P10103：基础错排与 djq 分治

· · 题解

题目链接

首先由于 i\leq m 的位置都满足 p_i>m，这样必然就满足了错排的条件。

可以从后 n-m 个较大的数中取 m 个与前面互换，这样答案就是 (n-m)^{\underline m} 乘以「从 n-m 个选项的中选 n-2m 个填到对应位置（像英语七选五那样），全错的方案数」再乘以 m!。最后乘的这个 m! 是因为从前 m 个位置取来的元素，在剩下的位置可以随意排列。

那么现在的问题就是计算这个「n 选 m 全错」的方案数，直接枚举至少选对了 j 个做容斥，就得到方案数为

b_{n,m}=\frac{1}{(n-m)!}\sum_{j=0}^m\binom mj(-1)^j(n-j)!

设 T(n,m)=(n-m)!b_{n,m}，考虑其在 m 这一维方向上的递推，可以算出

(n-m)T(n,m+1)=mT(n,m-1)-(1+2m-n)T(n,m)

你问这个递推式咋来的？我们把 T(n,m) 的式子改写为

\begin{aligned}T(n,m) &=\sum_{j=0}^m \binom mj (-1)^j (n-m+(m-j))! \\ &=m![x^m] \text e^{-x} \left( \sum_{j=0}^\infty \frac{(n-m+j)!}{j!}x^j\right)\end{aligned}

后面这个级数的 ODE 很容易从其递推式得出，这样就能得到 T(n,m) 的横向递推。

回到原问题，由此可以设向量和方阵

\bold V_{n,m}=\begin{bmatrix} n^{\underline{m-1}}T(n,m-1) & n^{\underline m}T(n,m)\end{bmatrix} \bold M_m(n)=\begin{bmatrix} 0 & m(n-m+1) \\1 & n-2m-1\end{bmatrix}

这样就可以写成矩阵转移：\bold V_{n,m+1} = \bold V_{n,m} \times \bold M_m(n)，即：

\bold V_{n,m}=\begin{bmatrix} n! & n!(n-1)\end{bmatrix} \times \prod_{i=1}^{m-1}\bold M_i(n)

这个是经典问题（人称 djq 分治），对于给定的多组 n,m 快速计算这些矩阵的乘积即可。这个做法有一个优势，就是只用推导 T(n,m) 横向的变化，而且时间复杂度更优秀。

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