【P7438】更简单的排列计数
飞雨烟雁
·
·
题解
本题解提供一种无需生成函数的做法。
注：以下所有排列 \pi 均为错排，|\pi| 表示排列 \pi 的长度。
记 c_{n,i}=\sum_\pi[|\pi|=n][\text{cyc}_ \pi=i]，即在长度为 n 的错排中，恰能分解为 i 个循环的排列个数。先列个关于 c_{n,i} 的表：
| n,i |
1 |
2 |
3 |
| 2 |
1 |
|
|
| 3 |
2 |
|
|
| 4 |
6 |
3 |
|
| 5 |
24 |
20 |
|
| 6 |
120 |
130 |
15 |
不难发现 c_{n,i}=(n-1)(c_{n-1,i}+c_{n-2,i-1})，以下证明：
对长度为 n 的排列 \pi 的最后一个数所在循环长度进行分类讨论：
-
显然其循环长度不可能为 1。
-
若其循环长度为 2，则将这个数字和与它构成循环的那个数一起拿走，剩下一个长度为 (n-2) 的错排。因为原错排有 i 个循环，现拿掉了一个循环，故剩下 (i-1) 个循环，所以剩余部分有 c_{n-2,i-1} 种方案。对于拿掉的那两个数，一个必须是 \pi_n，另一个是 1\sim n-1 中任意一个，有 (n-1) 种情况。
-
若其循环长度大于等于 3，则将 \pi_n 拿走，并让指向 \pi_n 的那个数指向 \pi_n 所指的那个数（见下例）。那么剩下的 (n-1) 个数仍是错排，且循环数为 i，故方案数为 c_{n-1,i}。对于 \pi_n，它原先可以插在任意一个数的前面，共有 (n-1) 个位置可插。
\begin{pmatrix}1&2&3&4\\2&4&1&3\end{pmatrix}\rightarrow\begin{pmatrix}1&2&3\\2&3&1\end{pmatrix}
综上，方案数为 c_{n,i}=(n-1)(c_{n-1,i}+c_{n-2,i-1})。
再看题目要求，记 \text{Ans}_ m=\sum_{|\pi|=m}F(\text{cyc}_ \pi)，F(x)=\sum_if_ix^i。
若直接展开 F(\text{cyc}_ \pi) 则得：
\begin{aligned}
\text{Ans}_ m&=\sum_{j}f_j\sum_{|\pi|=m}(\text{cyc}_ \pi)^j\\
&=\sum_{j}f_j\sum_ic_{m,i}\,i^j
\end{aligned}
记 b_{m,j}=\sum_ic_{m,i}\,i^j，可以证明有递推式：
b_{m,j}=(m-1)(b_{m-1,j}+\sum_{i=0}^j\binom jib_{m-2,i})
但是要是这样递推下去，时间复杂度是 O(n^3) 的，不如不要。
考虑采用 P4827 中的方法，用第二类斯特林数展开普通幂。因为：
m^n=\sum_{i=0}^ni!\binom mi\begin{Bmatrix} n \\i \end{Bmatrix}
所以可以用这个东西展开 (\text{cyc}_ \pi)^j，代入原式有：
\begin{aligned}
\text{Ans}_ m&=\sum_{j=0}^{k-1}f_j\sum_{|\pi|=m}\sum_{i=0}^ji!\binom {\text{cyc}_ \pi}i\begin{Bmatrix} j \\i \end{Bmatrix}\\
&=\sum_{i=0}^{k-1}\Bigg(i!\sum_{j=i}^{k-1}f_j\begin{Bmatrix} j \\i \end{Bmatrix}\Bigg)\sum_{|\pi|=m}\binom {\text{cyc}_ \pi}i
\end{aligned}
记 p_{m,i}=\sum_{|\pi|=m}\binom{\text{cyc}_ \pi}{i}，列表观察：
| m,i |
0 |
1 |
2 |
| 2 |
1 |
1 |
0 |
| 3 |
2 |
2 |
0 |
| 4 |
9 |
12 |
3 |
| 5 |
44 |
64 |
20 |
发现 p_{m,i}=(m-1)(p_{m-1,i}+p_{m-2,i}+p_{m-2,i-1})，以下证明：
\begin{aligned}
p_{m,i}&=\sum_{|\pi|=m}\binom{\text{cyc}_ \pi}i\\
&=\sum_{j}\binom jic_{m,j}\\
&=(m-1)\sum_{j}\binom ji(c_{m-1,j}+c_{m-2,j-1})\\
&=(m-1)\Big(p_{m-1,i}+\sum_{j}\binom {j-1}{i}c_{m-2,j-1}+\sum_{j}\binom {j-1}{i-1}c_{m-2,j-1}\Big)\\
&=(m-1)(p_{m-1,i}+p_{m-2,i}+p_{m-2,i-1})
\end{aligned}
证毕，则可在 O(nk) 的时间内把所有的 p_{m,i}(m\le n, i<k) 求出。
关于 i!\sum_{j=i}^{k-1}f_j\begin{Bmatrix} j \\i \end{Bmatrix} 这一部分，可以暴力 O(k^2) 求出。
至此，本题可在 O(nk+k^2) 的时间复杂度内完成。