P11316题解

· · 题解

P11316

尝试复健。

如果直接正向考虑 M 不整除的情况，太复杂，所以考虑算出不好的排列，然后拿总数减去它。

总数可以直接算出来，故不细说。考虑 f[i] 表示一共有 i 对 dist 被 M 整除的数对的排列个数。这个直接做有点难，但是可以设 f[i] 表示一共有 \ge i 对不好的数对的排列个数，然后作容斥。

我们把整个序列每 M 个切一段，那么 \bmod\ M 同余的位置在每个段内相对位置相同，我们要做的就是在这些位置中取出若干对位置进行计数。具体地，设当前枚举 \bmod{\ M}=i，枚举选出 j(2 \mid j) 个位置转移，则有方程（设 tot 为整个序列中 \bmod M=i 的位置个数）：

f[i] \times \binom{tot}{j} \times \binom{j}{\frac{j}{2}} \times j! \rightarrow f[i+\frac{j}{2}]

即 tot 个位置中选 j 个 \times 分配颜色方案数 \times 选出的 j 个数顺序。

然后，我们已经选出了 j 对，对于剩下的 n-\frac{j}{2} 个数，依据上面的方式继续乘以 颜色分配方案数 乘以 颜色顺序即可。

以上我们即可求出 f[i] 表示 \ge i 对不好数对的方案数，最后乘以一个 (-1)^{i+1} 的系数累加即可得到不好的排列个数，拿最开始的方案数即 \binom{2 \times n}{n} 减去即可。

复杂度 O(n^2)。