P4722 小球和盒子（基础）

解题思路

这道题是一个经典的"错排"问题。有 n 种颜色的小球和 n 种颜色的盒子，颜色相同的小球和盒子算一套。现在要求每个小球都不能放进和自己颜色配套的盒子里，问有多少种放法。

我们可以先想简单的情况。当 n=1 时，只有一个小球一个盒子，小球必须放进自己的盒子，所以完全错误的放法是 0 种。当 n=2 时，球 1 不能放盒子 1，只能放盒子 2；球 2 只能放盒子 1，所以正好有 1 种错排。

对于更大的 n，我们可以用错排公式：D(n) = (n-1) × (D(n-1) + D(n-2))。这个公式可以这样理解：先把第 1 个球拿出来，它不能放在盒子 1 里，所以它有 n-1 种选择，假设它放在了盒子 2。这时候看第 2 个球：如果第 2 个球正好放在盒子 1 里，那么剩下的 n-2 个球和 n-2 个盒子还是一个错排问题，有 D(n-2) 种放法；如果第 2 个球不放在盒子 1 里，那我们可以把"盒子 1"看成是第 2 个球要错开的盒子，问题就变成了 n-1 个球的错排，有 D(n-1) 种放法。所以总共有 (n-1)×(D(n-1)+D(n-2)) 种。

举个例子：n=3 时，D(3)=(3-1)×(D(2)+D(1))=2×(1+0)=2，正好和样例一致。n 最大是 9，错排数 D(9) 约 13 万多一点，但用 long long 更保险，也为以后数据变大留出空间。

这道题体现了把大问题拆成小问题、再从小问题的答案推出大问题答案的"递推"思想，是一道很好的入门递推题。

再举一个大一点的例子帮助理解：n=4 时，D(4)=3×(D(3)+D(2))=3×(2+1)=9。也就是说 4 个球全部放错一共有 9 种放法，同学们可以试着把 4 个球的错排全部列出来验证一下，比如球 1 放盒子 2、球 2 放盒子 1、球 3 放盒子 4、球 4 放盒子 3 就是一种。错排问题在生活中有很多实际应用：寄信时把 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[15];
    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 最大只有 9，几乎是瞬间完成。空间上只开了一个长度为 15 的小数组，空间复杂度 O(n)，同样非常小。