数学、动态规划

假设有 $m$ 个位置满足 $a_i=i$，先钦定所有 $a_i=i$ 的位置，有 $C_{n}^{m}$ 种钦定方案。

错误排列：不存在 $a_i=i$ 的 $i$ 的排列。

其余位置满足 $a_i \neq i$，求出长度为 $n-m$ 的错误排列数量，乘上方案数即可。

虽然不符合 $a_i=i$ 的位置可能并不构成排列，但是必然可以和排列的元素一一对应，然后替换。

设计 $dp_{n}$ 为长度为 $n$ 的错误排列数量，考虑如何得到 $dp_{n}$。

Solution 1：

• 可以在长度为 $n-1$ 的错误排列后插入 $n$，然后交换 $a_n$ 和 $a_i(i \leq n-1)$，容易证明得到的还是一个错误排列。
• 上述过程由于错误排列的性质无法得到 $n$ 在位置 $k$ 而 $k$ 在位置 $n$ 的错误排列，但可以从长度为 $n-2$ 的错误排列扩展得到这样的错误排列。共有 $n-1$ 个可能的 $k$ 值。

$$dp_{i}=(i-1)(dp_{i-2}+dp_{i-1})$$

Solution 2：

容斥，使用 $f_i$ 表示至少有 $i$ 个满足 $a_i = i$ 的位置的长度为 $n$ 的排列数量，得到 $f_i = C_{n}^{i} (n-i)!$。

$$dp_{n} = \sum\limits_{i=0}^{n} (-1)^{i} f_{i} = \sum\limits_{i=0}^{n} (-1)^{i} C_{n}^{i} (n-i)!$$

题目有多组数据，需要快速计算 $dp_{1} \sim dp_{10^6}$，继续推导。

$$dp_{n} = \sum\limits_{i=0}^{n} (-1)^{i} \cfrac{n!}{i!(n-i)!} (n-i)! = \sum\limits_{i=0}^{n} (-1)^{i} \cfrac{n!}{i!} = n! \sum\limits_{i=0}^{n} \cfrac{(-1)^{i}}{i!}$$

可以 $O(1)$ 完成从 $n!$ 向 $(n+1)!$ 的转移和从 $\sum\limits_{i=0}^{n} \dfrac{(-1)^{i}}{i!} 向 \sum\limits_{i=0}^{n+1} \dfrac{(-1)^{i}}{i!}$ 的转移，分开计算。

注意实现中递推结束后应当将 $dp_0$ 赋值为 $1$ 以满足计算需求（当 $n=m$ 时答案为 $1$）。

两种解法的时间复杂度都为 $O(T+n)$，注意特判 $m>n$ 的情况。