P4724 书架放书（基础）

解题思路

这道题和"错排问题"一模一样。书架上有 n 本书，每本书都不放在自己最初的位置上，问有多少种摆法。数学上称这种"没有一个元素在它原来的位置"的排列叫"错排"。

我们设 d[i] 表示 i 本书全部错开原来位置的摆法种数。先看最小的规模：1 本书时，它只能放在自己的位置上，所以没有错排，d[1]=0；2 本书时，两本书交换位置，正好都离开了原位置，d[2]=1。

当 i 本书时，我们推导错排公式。先把第 1 本书拿出来，它不能放在位置 1，所以有 i-1 个位置可以选择。假设它放在了位置 2。这时看第 2 本书：(1) 如果第 2 本书放在位置 1，那么剩下的 i-2 本书仍然是一个错排问题，有 d[i-2] 种；(2) 如果第 2 本书不放在位置 1，那么可以把位置 1 看成第 2 本书"要错开"的位置，问题就变成 i-1 本书的错排，有 d[i-1] 种。于是 d[i] = (i-1)×(d[i-1]+d[i-2])。

举个例子：3 本书时，d[3]=2×(d[2]+d[1])=2×(1+0)=2，和样例一致。可以自己动手列举一下：3 本书 1、2、3，错排只有 231 和 312 两种。

注意数据范围：n 最大是 20，d[20] 大约是 8.95×10^17，这个数已经超过 int 能表示的范围（int 最大约 21 亿），所以必须使用 long long 类型，否则会溢出出错。这也是本题的一个小陷阱。

再验证一个稍大的例子：n=4 时，D(4)=3×(D(3)+D(2))=3×(2+1)=9。也就是说 4 本书全部不在原位置有 9 种摆法。我们可以列举验证：4 本书记为 1、2、3、4，错排一共有 9 种，例如 2143、2341、2413、3142 等等，数一数正好 9 种，和公式算出来一致。错排问题在生活中非常常见：把 n 封信全部装错信封、让 n 个同学全部坐在与自己编号不同的座位上、把 n 份礼物全部送错人，都是同一个数学模型。以后遇到这类"谁也不在原位"的排列计数题，直接套用错排公式 d[i]=(i-1)×(d[i-1]+d[i-2]) 就能快速求解，不用再一个一个枚举了。

参考代码

// 书架放书：每本书都不在原来位置，完全错排问题
#include <iostream>
using namespace std;
int main(){
    int n;
    cin >> n;
    long long d[25];
    d[1] = 0; d[2] = 1;  // 1本书无错排，2本书只有1种错排
    for (int i = 3; i <= n; i++)
        d[i] = (i - 1) * (d[i-1] + d[i-2]);
    cout << d[n] << endl;
    return 0;
}

复杂度分析

程序用一层循环从 3 递推到 n，每一步做一次乘法和两次加法，时间复杂度是 O(n)。n 最大为 20，运行时间几乎为零。空间上只用了一个长度 25 的 long long 数组，空间复杂度 O(n)，非常节省。