题解：AT_abc247_h [ABC247Ex] Rearranging Problem

· · 题解

Solution

考虑对排列 p，计算哪些 k 使得 p 进行 k 次交换后能变为 \{1,2,3,\cdots,n\}。

设其逆序对数为 \tau(p)，显然应当有 k \equiv \tau(p) \bmod 2。而如果 k 有解，k+2 一定有解，所以我们只需要找到 k_{\min} 即可。对于本题，需要满足 k_{\min} \le k 且 k_{\min} \equiv k \pmod 2。

怎么计算 k_{\min} 呢。将 p 刻画为若干个置换环。每次 \text{swap}(p_i,p_j)，带来的影响是：

  1. 如果 i 和 j 在同一个置换环中，会将该置换环分裂成两个；
  2. 如果 i 和 j 不在同一个置换环中，会将两个置换环合并。

我们的目标是将置换环分裂成 n 个。因此设 p 具有的置换环个数为 cnt，k_{\min} = n - cnt。

本题就转化为：给定序列 \{c\}，问有多少个排列 p 使得 c_i = c_{p_i} 且 p 的置换环数量 = cnt。

对于同一种 c 内部（假设有 d 个 c），置换环为 cnt 可以直接由 [x^{cnt}]\prod_{i=0}^{d-1}(x+i) 维护（第一类斯特林数）。

所以整个 cnt 就可以写成 \prod_{i=0}^{n-1} (x+i)^{\sum_{c} [d_c > i]}。

单项式个数的和为 \sum d_c = n，所以可以直接分治 NTT。

复杂度 O(n \log^2 n)。

代码没写，因为 NOI 不考 NTT。