组合计数·题目演练

· · 算法·理论

前言

组合计数其实一直都挺头疼的，因为每次考场上都看不出来这题还要用到一些奇怪的排列组合。有一类很经典的区间动态规划题目中间的符号数方案经常漏乘，因为看不出来排列组合。

NOIP 2024 第二题是排列组合题目，NOIP 2025 第二题也是排列组合题目。真的害怕 NOIP 2026 第二题又塞个排列组合题目。畏惧了。

缺失基本理论可以看上一篇。

本文题单来自能力提升综合题单 Part 6 数学 2和个人总结。

《能力综合提升题单》部分

P3807 【模板】卢卡斯定理 / Lucas 定理

看起来可以直接套组合数公式，但是处理的中间会发现阶乘一旦超过 p 就得直接挂，所以还得用点高级的化简技巧。

卢卡斯定理：

\binom{n}{m} \equiv \binom{\lfloor \dfrac{n}{p} \rfloor}{\lfloor \dfrac{m}{p} \rfloor}\binom{n \bmod p}{m \bmod p} \pmod p

多次操作后可以将组合内部的数降至 p 以下，此时就可以直接套公式做了。

int C(int n, int m){ 
    if (n < m) return 0;
    if (n < MOD && m < MOD) return 1ll * fac[n] * ifac[m] % MOD * ifac[n-m] % MOD;
    return 1ll * C(n / MOD, m / MOD) * C(n % MOD, m % MOD) % MOD;
}

P2822 [NOIP 2016 提高组] 组合数问题

这道题数据范围一大就要挂，因为连模数都没给。

当然套组合数公式貌似行不通了，考虑换一种方法计算组合数，看到数据范围允许 O(n^2) 可以想到杨辉三角。

考虑是倍数实际上就是对 k 取模余数是 0，但这题多测很讨厌，如果直接算三角每次暴力统计时间复杂度是 O(Tn^2)，挂掉了。

考虑每个询问本质上考虑的是一个子三角形（可直接视作矩形），可以在预处理时直接处理出所有答案，时间复杂度 O(n^2 + T)。

int main(){
    cin >> T >> k;
    C[0][0] = 1;
    for (int i = 1; i < N; i++){
        C[i][0] = 1;
        for (int j = 1; j <= i; j++){
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % k;
            ans[i][j] = ans[i - 1][min(i - 1, j)] + ans[i][min(i, j - 1)] - ans[i - 1][min(i - 1, j - 1)] + (C[i][j] == 0);
        }
    }
    while (T--){
        int n, m; cin >> n >> m;
        cout << ans[n][min(n, m)] << endl;
    }
    return 0;
}

P5520 [yLOI2019] 青原樱

考虑隔板法计数，即在树苗之间空格的 n - m + 1 个位置中插入 m 个树苗，每个位置只能放至多一个。

请注意为什么不拿树苗作为位置，让空格插入，因为空格可以连续存在多个，难以统计，但是树苗不行，故以空格作为位置，让树苗插入。此时所有间隔及两端均可插入。

然后树苗在此题目中两两不同，则对于第 i 个位置有 m - i + 1 种选择方案，输出所有选法的乘积即可。

P3197 [HNOI2008] 越狱

直接统计有多少种方案不合法显然不太方便，不妨利用容斥原理，求出相邻两个位置的宗教均不相同的方案数，再用总方案数扣除该部分即为答案。

则总方案数为每个房间随便选一个宗教的方案数，即为 n^m，相邻两个位置均不相同时：

即最终答案为 n^m - m(m-1)^{n-1}。套个快速幂即可。

注意最后要输出一个非负整数。

P2290 [HNOI2004] 树的计数

一个合法的方案的度数总和应该总是 2n - 2，因为每棵合法的树都有 n - 1 条边。除此以外，仅 n = 1 时度数应该为 0。

对于一棵节点数为 n 的无根树，存在一种 prufer 序列与其一一对应，其生成方法为找到度数为 1 的点并删除其所有连边，将其所有连边的点加入序列。这样生成的序列有 n - 2 个数。

考虑每个点可以任选 d_i - 1 个格子占上位置作为自己的子节点的位置，共有 n - 2 个位置，故答案为：

\prod_{i = 1}^n \binom{n - 2 - \sum_{j = 1}^{i - 1} (d_j - 1)}{d_i - 1}

又没有模数，好在本题数据范围允许预处理，故预处理出所有需要的组合数，时间复杂度 O(n^2)。

P4981 父子

这题目背景真心绷不住了。

考虑任选一个人作为树的根节点，共 n 种方案。其他人任选一个人给他当父节点，不能选自己故每个人各有 n - 1 种方案数，则答案为这么考虑显然错误。

这么考虑的话，如果两个人互相为父亲就挺没救的，所以我们还得用上一道题用的 prufer 序列。

由于 prufer 序列处理的是无根树，而这道题有根，则任选一个根还有 n 种方案。

上一题说到 prufer 序列和无根树一一对应，且其长度为 n - 2，则共有 n ^ {n - 2} 种方案构造该序列。

注意还有选根的方案，故最终答案为 n ^ {n - 1}。

P4769 [NOI2018] 冒泡排序

别笑，你来你也过不了第二关。

本题解参考了其他题解，原题解链接。

概括：求字典序严格大于排列 q 的排列中有多少排列能取到理论下界。

考虑理论下界什么时候能取到，即交换两个数的时候应该都更靠近自己排序后的位置。由证明部分提示，如果有长度超过 2 的下降子序列就会超过理论下界。由 Dilworth 定理得最多被划分为 2 段上升子序列。

忽略字典序限制，考虑 f_{i, j} 为前 i 个数最大值为 j 时，后面 n - i 个数的方案数。如果第 i 个数填比 j 大的数，则一定可以放在下一位，否则只能填目前没有填过的最小的数。故有 f_{i, j} = \sum_{k = j}^n f_{i + 1, k}。

然后递推就炸了，时间复杂度 O(n^2)。

以图像形式表示，f_{i, j} 表示从 (i, j) 向右一步，向上 x 步，不与 y = x - 1 相交走到 (n, n) 的方案数。

忽略不与直线相交条件，走 n - i 次，向上走 x 步，且 \sum x = n - j 的方案数。插板法，等价于把 n - j (+ n - i) 个物品划分为 n - i 块的方案数，因为可能有 x = 0 故要加 n - i，即方案数为 \dbinom{2n - i - j - 1}{n - i - 1}。

回到不与直线相交条件，模仿 Catalan 数，找第一次与直线相交的位置。点 (i, j) 关于 y = x - 1 的对称点 (j + 1, i - 1)，由于方案一一对应，从 (i, j) 出发经过直线到达即为从 (j + 1, i - 1) 出发到点 (n, n) 的方案数。

则 f_{i, j} = \dbinom{2n - i - j - 1}{n - i - 1} - \dbinom{2n - i - j - 1}{n - j - 2}。

回到字典序限制，考虑枚举到第 i 项，前 i - 1 位与 q 相同，后面大于 q 的方案数。

记 a 为 q 前 i - 1 项的最大值，b 为最小的未被使用的元素，第 i 位只能填大于 a 或者等于 b 的数，则：

求 f 的前缀和时，考虑 f 的递推式，正好是前缀和的形式，则：

\sum_{p}^{n} f_{i, k} = f_{i - 1, p}

时间复杂度 O(Tn)。

P4931 [MtOI2018] 情侣？给我烧了！（加强版）

考虑选出 k 对情侣和睦，则需要选 k 排座位共 \dbinom{n}{k} 种，选 k 对情侣共 \dbinom{n}{k} 种，排列顺序共 k! 种，每排可以交换共 2^k 种。

对于错排部分，记 f_n 表示 n 对错排的方案数，对于这一排，任取一对不坐在一起的情侣，共有 2n(2n-2) 种方案数，考虑这两个人的另一半，则：

故 f_n = 2n(2n - 2)(2(n-1)f_{n-2} + f_{n-1})。

则最终答案为 \dbinom{n}{k}^2k!2^kf_{n - k}。

P5596 【XR-4】题

判断无限多解，将 x^2 移到右边：

y^2 = x^2 + ax + b

若右边完全平方了，显然有无限多个解，即 \Delta = a^2 - 4b = 0 时有无限多个解。

正常推导一下，看起来左边很想让你因式分解一下：

(y - x)(y + x) = ax + b

遇事不决就换元，令 k = y - x \in \mathbb{N}：

k(k + 2x) = ax + b k^2 + 2kx = ax + b b - k^2 = (2k - a)x x = \dfrac{b - k^2}{2k - a} \in \mathbb{N}

其中 f(k) = b - k^2 \searrow, g(k) = 2k - a \nearrow，由 x \in \mathbb{N}，枚举 k，当自然数 k 使得 f(k) < 0, g(k) > 0 时可提前跳出。

不知道组合计数为啥混进来一道数学题。

P5598 【XR-4】混乱度

容易发现 f(l, r) = \dbinom{\sum_{j = l}^{r} a_j}{a_l, a_{l+1}, \cdots, a_r} = \prod_{i = l}^r \dbinom{\sum_{j = i}^{r} a_j}{a_i}。

则题目所求即为：

\sum^{n}_{l=1}\sum^{n}_{r=l+1}\prod_{i = l}^r \dbinom{\sum_{j = i}^{r} a_j}{a_i}

发现题目所求是一个 \dbinom{n + m}{n} 的形式，易得在 n + m \le n \pmod p，即发生进位时，该组合数为 0。

对于固定的右端点 r，猜测其可能的左端点 l 所成的区间一定不会太长。考虑鸽巢原理，每一位最多加 p - 1 次，一共有 \log_p V 位，最多扩展 O(p \log_p V) 次。

不能重新计算组合数，否则时间复杂度会退化，考虑更新时没有进位导致所有位的更新次数是 O(p \log_p V)，每存在一位被更新就重新计算这一位即可。

时间复杂度 O(np \log_p V)。

自选部分

P5505 [JSOI2011] 分特产

对于一种数量为 x 的物品，分给 y 个人，每个人不一定要有的方案数可以隔板法计算（由于可以为空所以我们需要额外添加 y 个物品）：\dbinom{x + y - 1}{y - 1}，即 x + y 个物品有 x + y - 1 个空，要分成 y 份其中要放 y - 1 个板子的方案数。

记 f_i 表示至少有 i 个同学没有土特产的方案数，则首先从所有人中选出这 i 个人，然后对于每个物品进行相应计算，有公式：

f_i = \dbinom{n}{i}\prod_{j=1}^m\dbinom{a_j + n - i - 1}{n - i - 1}

则可以对所有情况直接套容斥原理公式：

ans = \sum_{i=\color{red}0}^n (-1)^i\dbinom{n}{i}\prod_{j=1}^m\dbinom{a_j + n - i - 1}{n - i - 1}

P1641 [SCOI2010] 生成字符串

考虑转化成图像处理，则答案等价于从点 (0, 0) 走到 (m, n)，且不与直线 y = x - 1 相交（y - x < 0 的最大整数解是 y - x = -1，即 y = x - 1）的方案数。

忽略该限制，则总方案数为 n + m 步中选 n 步向上，该部分答案为 \dbinom{n + m}{n}。

回到限制，考虑第一次与直线相交的位置。取 (0, 0) 关于 y = x - 1 的对称点 (1, -1)，则由于方案一一对应，从该点出发到 (m, n) 的方案数即为不合条件的方案数，向上走 n + 1 步，向右走 m - 1 步，类似地，该部分答案为 \dbinom{n + m}{n + 1}。

则最终答案为 \dbinom{n + m}{n} - \dbinom{n + m}{n + 1}。

P6076 [JSOI2015] 染色问题

考虑限制 4 做起来比较简单，故设当前限制最多 k 种颜色的方案数为 f_k，则：

ans = \sum_{i=0}^c (-1)^{c-i} \dbinom{c}{i}f_i

考虑 f_k 计算时也可以容斥，设当前最多 k 列有数，则：

f_i = \sum_{j=0}^m (-1)^{m-j} \dbinom{m}{j}((i + 1)^j - 1)^n

直接计算即可。

P3166 [CQOI2014] 数三角形

显然要容斥，任取三个点的方案数是 \dbinom{(n+1)(m+1)}{3}，去掉三点共线的所有情况就是三角形。

行列共线比较好算，分别是 (n+1)\dbinom{m+1}{3} 和 (m+1)\dbinom{n+1}{3}。

考虑斜着共线，枚举斜率 \dfrac{y}{x}，考虑本质上 -\dfrac{y}{x} 的共线方案数和 \dfrac{y}{x} 相等，故本题中仅考虑正斜率，并将其乘 2 即为总情况。

考虑 \Delta x = x, \Delta y = y 的点对数有 (n - x + 1)(m - y + 1) 组，而这两个点所在的线上有 \gcd(x, y) + 1 个点，再选一个点的方案数为 \gcd(x, y) - 1。

故最终答案为：

\dbinom{(n+1)(m+1)}{3} - (n+1)\dbinom{m+1}{3} - (m+1)\dbinom{n+1}{3} - 2\sum_{x=1}^n\sum_{y=1}^m (n - x + 1)(m - y + 1)(\gcd(x, y) - 1)

P7392 「TOCO Round 1」奇怪的排序

考虑其本质上是一个被限制 k 层的归并排序，则能完成排序当且仅当其被划分成 2^k 段后每段均有序。

一个长度为 m 的数列自然有序的概率为 \dfrac{1}{m!}。最终用该概率乘全排列即可。

则：