智障手抽人快速幂写错导致最后 1min 没有冲出 F
不过是我太菜了
A
不解释
不懂为什么 printf("%.0lf", a)
会 WA 最后一个点
吃了两发罚时,吐血了
B
不解释
C
还是不懂为什么拓扑排序过不了。直接从 $n$ 出发遍历一下图标记到达过的点就行了.....
D
看一下除掉 $\gcd$ 后不同的点对有多少就行了。注意 $\gcd$ 要绝对值.....
E
只能说多年英语白学了。 exactly
adv. 恰好 。假如你的翻译器没有翻译这个东西,或者你没注意到默认了是至少,那么你会卡死在这个题目。假如整个机房都没有看见,那么就是整个机房都会卡死在这个题目。
假如看见了,那么只有连通块只有呈一个环状即 $n=m$ 时合法,有两种方式。如果出现了一个不是环的连通块直接 return puts("0"),0
即可。否则 ans *= 2ll
。
F0
直接发现 $S(P)$ 就是排列 $P$ 的环长。直接考虑计算答案。
$$ n! \times \prod\limits_{L,F} \frac{1}{(L!)^F \cdot F!} ((L-1)!)^F $$
DFS 求一下划分即可。
F1
dp 计数。
把 $i \to p_i$ 连边,得到的图会有很多的环。假如现在有一个 $n$ 个点的图,那么我们根据这个图构造一个排列 $P$ ,但是可能的环的个数只有 $(n-1)!$ 个。
对于一个长度为 $n$ 的错排,把它们移回 1 2 3 ... n
这样的排列至少要 $n \cdot d (d >0)$ 次。因此,最终答案应该从环中划分出每个可能的最小的大小。即 lcm.
设 $f_{i,j}$ 表示当前的数的划分是 $i$ ,lcm 是 $j$ ,那么每次枚举一个 $x$ 转移:
$$ f_{i,j} \times \binom{n-i-1}{x-1} \times (x-1)! \to f_{i+x, LCM(j, x)} $$
最终答案:$\sum f_{n,m} \times s^k$
F2
还是上面那个 dp,但是实际上有用的状态很少,每次都只会从 $j$ 的质因数转移过来,只有 $100$ 左右。所有每次枚举质因数然后乘倍数即可。
顺利最优解
G
智慧题,懒得丢题解链接了。