某模拟赛题
对于任意 \(1\le k\le n\)，若有 \(v_k\) 个长度为 \(n\) 的错位排列中存在长度为 \(k\) 的循环节，即对于 \(p_{1\cdots k-1}\)，\(a_{p_i}=p_{i+1},a_{p_k}=p_1\)。求 \(\sum v\)。
首先考虑错排的限制，对于 \(n\) 个数，可能的错排排列数为 \(d_i\)。有结论：
\(d_i=(i-1)(d_{i-1}+d_{i-2})\)
考虑枚举 \(k\)，发现不好钦定恰好有 \(i\) 个循环节，于是考虑容斥钦定至少有 \(i\) 个循环节 \(w_i\)。则：
\(w_i={n\choose i\cdot k}\cdot \frac{(i\cdot k)!}{(\prod k!)^i\cdot j!}\cdot [(k-1)!]^i\cdot d_{n-i\cdot k}\)
假设恰好有 \(i\) 个循环节的情况数为 \(f_i\)，观察发现 \(w_i=\sum_{j\ge i}{j\choose i}f_j\)。
发现是二项式反演的形式。
\(f_i=\sum_{j\ge i}{j\choose i}(-1)^{j-i}w_j\)
于是现在可以 \(O(n^2)\) 计算。固定 \(k\)，从每个 \(w_i\) 的贡献角度观察。
发现后面 \(\sum_{i=1}^{j}{j\choose i}(-1)^{j-i}\) 的形式与二项式定理类似，\(\sum_{i=0}^{j}{j\choose i}(-1)^{j-i}\) 化简得 \(0^j=1=(-1+1)^j\)。
则 \(v_k=\sum_{j=1}^{\lfloor\frac{n}{k}\rfloor}w_j\cdot (-1)^j\)，于是就能 \(O(n\ln n)\) 计算。