题解：CF2226F Inversion Invasion

· · 题解

注意到因为 \gcd(x,n)=\gcd(n-x,n)，所以对于 p_i\neq n 的位置，p_i 换成 n-p_i 一定依旧合法。而两个排列对于任意 i,j(p_i\neq n,p_j\neq n)，逆序对的贡献又恰好为 1，所以 p_i\neq n 的位置贡献是固定的，每个排列期望贡献都是 \frac{1}{2}\binom{n-1}{2}。

所以只要考虑 n 对于逆序对的影响。如果没有确定 n 在哪，每个排列的期望贡献为 \frac{1}{c}\sum\limits_{a_i=0} n-i。其中 c 是 a_i=0 的数量。否则，就是贡献 n-p。

然后考虑计算有多少合法排列。对于已经确定 a_i 的位置，设 a_i=x 已经给出了 c_x 次，而 \gcd(i,n)=x 的 i 共有 d_x 个，则 \prod \binom{c_x}{d_x}\times d_x! 即为这部分贡献。然后 a_i 没确定的位置，九贡献一个 c!。

只需要预处理阶乘即可。\gcd(i,n)=x 本质是 \varphi(n/x)，所以可以线性筛预处理 \varphi(i)。复杂度即可做到 \mathcal O(n+q+V)。

https://codeforces.com/contest/2226/submission/396071950