深入解析组合计数与算法优化

核心逻辑与数学原理

组合计数是离散数学的核心。在 NOIP 竞赛中，所有复杂的计数模型最终都可以归结为三大基础支柱：排列组合通项、放球模型（隔板法）以及错位排列。

1. 排列与组合基础公式

• 排列数（Permutation）：从 $n$ 个不同元素中取出 $m$ 个元素排成一列的方案数。

$$A_n^m = \frac{n!}{(n-m)!} = n \cdot (n-1) \dots (n-m+1)$$

• 组合数（Combination）：从 $n$ 个不同元素中取出 $m$ 个元素组成一个集合（不计顺序）的方案数。

$$C_n^m = \frac{n!}{m!(n-m)!}$$

组合数满足对称性 $C_n^m = C_n^{n-m}$ 以及递推性质（杨辉三角公式） $C_n^m = C_{n-1}^{m-1} + C_{n-1}^m$。

2. 隔板法（放球模型）

用于解决 $n$ 个相同的球放入 $m$ 个不同的盒子 的计数问题。

• 情况 A：每个盒子至少放一个球（不为空）
  将 $n$ 个球排成一排，球与球之间形成 $n-1$ 个空隙。放入 $m-1$ 块隔板将球切分为 $m$ 部分，每部分对应一个盒子。方案数为：

$$C_{n-1}^{m-1}$$

• 情况 B：盒子允许为空
  引入虚拟筹码。假设我们向每个盒子预借 $1$ 个球，此时球的总数变为 $n+m$ 个。问题转化为“$n+m$ 个球放入 $m$ 个盒子且不为空”，根据情况 A 结论，方案数为：

$$C_{n+m-1}^{m-1}$$

3. 错位排列（Derangement）

全排列 $
$ 满足对于任意的 $i$，都有 $(i) eq i$。记 $n$ 个元素的错位排列数为 $D_n$。其数学递推公式为：

$$D_n = (n-1)(D_{n-1} + D_{n-2})$$

递推逻辑证明：
考虑第 $n$ 个元素放到了位置 $k$ （共有 $n-1$ 种选择，其中 $k eq n$）。

• 情况 1：若第 $k$ 个元素正好放到了位置 $n$。此时 $n$ 与 $k$ 互换位置，剩下的 $n-2$ 个元素独立进行错位排列，方案数为 $D_{n-2}$。
• 情况 2：若第 $k$ 个元素没有放到位置 $n$。此时可将位置 $n$ 视作原先位置 $k$ 的替身，剩下的 $n-1$ 个元素（包含元素 $k$）进行错位排列，方案数为 $D_{n-1}$。
  由加法原理和乘法原理直接导出公式。边界条件为 $D_1 = 0, D_2 = 1$。

状态设计与算法推导

在面对多组询问的线性范围内计数时，直接套用通项公式效率低下。我们通常需要利用状态预处理来达到 $O(1)$ 的响应速度。

• 组合数状态设计：对于常规大质数取模，预处理阶乘及其逆元（参见 19.6 章），在 $O(N)$ 预处理后通过 $O(1)$ 状态方程输出。
• 错位排列状态设计：
  定义一维状态数组 $D[i]$ 表示大小为 $i$ 的全错位排列数。
  状态转移方程极其纯粹：

$$D[i] = (i - 1) \cdot (D[i - 1] + D[i - 2]) \bmod \text{MOD}$$

该转移仅依赖前驱两项，可在线性扫描中以 $O(N)$ 复杂度填满状态表。

C++ 标准源码

#include <iostream>
#include <vector>

const int MOD = 1000000007;
const int MAXN = 1000000;

long long fact[MAXN + 5];
long long invFact[MAXN + 5];
long long D[MAXN + 5];

// 快速幂
long long quick_power(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp & 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp >>= 1;
    }
    return res;
}

// 预处理组合数学基础状态与错排状态
void init_structures(int n) {
    // 1. 预处理组合数
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = (fact[i - 1] * i) % MOD;

    invFact[n] = quick_power(fact[n], MOD - 2);
    for (int i = n; i >= 1; --i) invFact[i - 1] = (invFact[i] * i) % MOD;

    // 2. 预处理错位排列状态
    D[1] = 0;
    D[2] = 1;
    for (int i = 3; i <= n; ++i) {
        // 严格带模加法，防止括号内相加后爆发越界
        D[i] = (i - 1) * ((D[i - 1] + D[i - 2]) % MOD) % MOD;
    }
}

// O(1) 获取组合数
long long C(int n, int m) {
    if (m < 0 || m > n) return 0;
    return fact[n] * invFact[m] % MOD * invFact[n - m] % MOD;
}

// O(1) 解决盒子可空的放球模型：n个同球入m个异盒
long long balls_in_boxes(int n, int m) {
    return C(n + m - 1, m - 1);
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    init_structures(MAXN);

    int t;
    if (std::cin >> t) {
        while (t--) {
            int n, m;
            std::cin >> n >> m;
            // 示例：输出从n个元素选m个的组合数，以及n个元素的错排数
            std::cout << C(n, m) << " " << D[n] << "\n";
        }
    }
    return 0;
}

NOIP 实战避坑指南

1. 错位排列乘法分配律漏取模导致数据越界
   在执行 D[i] = (i - 1) * (D[i - 1] + D[i - 2]) 时，内部 D[i - 1] + D[i - 2] 的最大值可能接近 $2 \times 10^9$。如果不加括号及时取模，再乘上外侧的 (i - 1)（若 $i \approx 10^6$），中间结果会达到 $2 \times 10^{15}$，直接把 int 撑爆引发符号位反转。必须严格保证每一步加法与乘法后都有 % MOD。
2. 放球模型变式中混淆“球同”与“球异”
   隔板法仅适用于球相同、盒子不同的情况。如果题目描述为“$n$ 个不同的球放入 $m$ 个不同的盒子”，部分选手还会惯性套用 $C_{n+m-1}^{m-1}$，这会导致逻辑全盘崩溃（异球入异盒本质上是第二类斯特林数或通道计数模型 $m^n$）。审题时必须敏锐捕捉“相同”与“不同”的限定词。

经典 NOIP/洛谷 真题

1. 洛谷 P4071 [SDOI2016] 排列计数

• 题意描述：求有多少个长度为 $n$ 的排列，恰好有 $m$ 个位置满足 $(i) = i$（即恰好有 $m$ 个稳定点）。结果对 $10^9+7$ 取模。
• 问题本质：组合选择与错位排列的乘法原理复合模型。
• 核心解题思路：首先从 $n$ 个位置中任选 $m$ 个位置作为稳定点，方案数为 $C_n^m$。确定了这 $m$ 个位置后，剩下的 $n-m$ 个位置必须全部错位排列，方案数为 $D_{n-m}$。根据乘法原理，最终答案即为 $C_n^m \cdot D_{n-m} \bmod \text{MOD}$。直接利用上文源码中的双状态预处理表，即可实现 $O(1)$ 单次响应。

2. 洛谷 P3182 [HAOI2016] 放戏

• 题意描述：有 $n$ 个位置，每个位置上初始各有一个球，编号为 $1 \sim n$。现在要求重新安排这些球的位置，使得每个球都不在原本的位置上，且球的相对顺序不能发生某种特定的循环（即特定的错排规则）。
• 问题本质：大数全错位排列计数（需要高精度或大模数支撑）。
• 核心解题思路：本质上就是纯粹的错位排列计数模型。通过建立状态转移方程 $D_n = (n-1)(D_{n-1} + D_{n-2})$。注意部分题目无取模要求，需使用 __int128_t 或高精度加法/乘法来递推该状态表。