组合计数基础

组合计数是组合数学的基础，研究某组离散对象满足一定条件的安排的存在性、构造及计数等问题。看似名字人畜无害，实则“算死人，不偿命”。本文将引导你学习简单的组合计数，为接下来学习毒瘤的计数问题作准备。

基本概念

组合计数中有一些基本概念，在这里简略地进行介绍。

加法原理

比如 james1 要吃东西，他可以吃傻瓜果和笨蛋果两种果子，市面上在售的傻瓜果有 $3$ 种，笨蛋果有 $4$ 种，如果 james1 只吃一颗果子就能吃饱，那么他就有 $3+4=7$ 种选择去吃饱。
形式化地，完成一个 Project 可以有 $n$ 类办法，$a_i$ 代表第 $i$ 类方法的数目。那么完成这个 Project 共有 $S=a_1+a_2+\cdots+a_n=\sum\limits_{i=1}^{n}a_i$ 种不同的方法。

乘法原理

比如 james1 要变傻（雾），要吃一种傻瓜果和一种笨蛋果，市面上在售的傻瓜果有 $3$ 种，笨蛋果有 $4$ 种，那么 james1 变傻的方式就有 $3 \times 4 = 12$。
形式化地，完成一个 Project 可以有 $n$ 个步骤，$a_i$ 代表完成第 $i$ 步的方法数目。那么完成这个 Project 共有 $S=a_1 \times a_2\times\cdots\times a_n=\prod\limits_{i=1}^{n}a_i$ 种不同的方法。

抽屉原理（鸽笼原理）

常用于存在性证明与极端情况求解，分为两种情况：

简单形式

james1 要将 $n+1$ 个笨蛋果放到 $n$ 个鸽笼中，那么可以得出至少有一个鸽笼中有两个（或以上）笨蛋果。

证明：

证毕。

推广

james1 要将 $n$ 个傻瓜果放到 $k$ 个鸽笼中，那么可以得出至少有一个鸽笼中有大于或等于 $\lceil \cfrac{n}{k} \rceil$ 个笨蛋果。

证明同样采用反证法，留给读者撕烤。

排列数

从 $n$ 个不同元素中，任取 $m$（$m\leqslant n$）个元素按照一定的顺序排成一列，方案个数记作 $A_{n}^{m}$（推荐）或 $P_{n}^{m}$。

显然，第一个数有 $n$ 种取法。
第二个数有 $n-1$ 种。
$\dots$
第 $m$ 个数有 $n-m+1$ 种取法。

综上所述，有：

$$A_{n}^{m}=n(n-1)(n-2)\cdots(n-m+1)=\cfrac{n!}{(n-m)!}$$

置换和排列

一个有限集合 $S$ 到自身的双射称为 $S$ 的一个置换，集合 $S={a_1,\cdots,a_n}$ 的置换可以表示为：

$$f=\begin{pmatrix}a_1,a_2,\dots,a_n\\ a_{p_1},a_{p_2},\dots,a_{p_n} \end{pmatrix}$$

是将 $a_i$ 映射为 $a_{p_i}$，这样 $p$ 是 $1\cdots n$ 的一个排列，$S$ 上的所有置换的数量为 $n!$。

置换的过程可以使用有向图来理解，连边 $i\rightarrow p_i$，就是所有点移动 $1$ 的距离。

对于两个置换 $f,g$ 的乘积记作 $f\circ g$，代表先通过 $f$ 的映射，再通过 $g$ 的映射。

一个排列中的逆序对个数，也叫做反序数，如果是偶数就是偶排列，奇数则是奇排列。

对于一个排列 $1,\cdots,n$，如果将任意两个数 $i,j$ 交换，其它数保持不动，就会得到一个新的排列，那么这样一个变换叫做对换，用 $(i,j)$ 表示。

组合数

从 $n$ 个不同元素中，任取 $m$（$m\leqslant n$）个元素按照任意的顺序组成一个集合，方案个数记作 $C_{n}^{m}$。

这 $m$ 个人是没有顺序的，所以 $A_{m}^{m}$ 个方案是同一个方案，所以总方案数为：

$$C_{n}^{m}=\cfrac{A_{n}^{m}}{A_{m}^{m}}=\cfrac{n!}{(n-m)!} \div m! = \cfrac{n!}{(n-m)!m!}\\ C_{n}^{m}=\cfrac{A_{n}^{m}}{A_{m}^{m}}=\cfrac{n(n-1)(n-2)\cdots(n-m+1)}{m!}=\cfrac{\prod_{i=n-m+1}^n i}{m!}$$

实际上，组合数也通常用 $\dbinom{n}{m}$ 表示，相当于 $C_{n}^{m}$，这也被称之为二项式系数。

组合数有以下性质：

1. $C_{n}^{m} = C_{n}^{n-m}$；
2. $C_{n}^{0}+C_{n}^{1}+C_{n}^{2}+\cdots+C_{n}^{n}=\sum\limits_{i=0}^{n}C_{n}^{i}=2^n$；
3. $\dbinom{n}{k}=\cfrac{n-k+1}{k}\dbinom{n}{k-1}$。

证明：

int C(int n, int m) {
	int res = 1;
	for (int i = 1; i <= m; ++i)
		res = 1ll * res * (n - i + 1) / i;
	return res;
}

然后是一些不是那么好想，但是在关键时刻非常有用的内容，推荐背诵：

1. $\dbinom{n}{m}=\cfrac{n}{m}\dbinom{n-1}{m-1}$；
2. $\sum\limits_{i=0}^m\dbinom{n}{i}\dbinom{m}{m-i}=\dbinom{m+n}{m}(n\ge m)$，当 $n=m$ 时有 $\sum\limits_{i=0}^{n}{\dbinom{n}{i}}^2=\dbinom{2n}{n}$；
3. $\sum\limits_{i=0}^{n}\dbinom{i}{k}=\dbinom{n+1}{k+1}$；
4. $\dbinom{n}{r}\dbinom{r}{k}=\dbinom{n}{k}\dbinom{n-k}{r-k}$，相当于是 $n$ 只喵喵中选 $r$ 个队长，再在队长中选择 $k$ 个大队长，等价于 $n$ 只喵喵先选 $k$ 个大队长再选 $r-k$ 个队长，因为大队长也是队长。

杨辉三角

杨辉三角长这样（所有的空格值都为 $0$）：

可以观察出 $C_{n}^{m}=C_{n-1}^{m}+C_{n-1}^{m-1}$。

证明：

所以组合数的杨辉三角递推代码如下：

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] + C[i - 1][j - 1];
}

二项式定理

高中学过二项式定理：

$$(a+b)^n = \sum_{i=1}^{n}\binom{n}{i}a^{n-i}b^i$$

这个式子非常有用，一定要熟记。另外可以发现，多项式的系数就是杨辉三角。

排列组合方法

我们来看三个问题，来引出排列组合的经典计算方法。

捆绑法

$n$ 只兔子参观大连市第二十四中学，其中 $m$ 只兔子关系特别好，它们一定要站在一块。那么有多少种排列方法？

我们把这 $m$ 只兔子看作一只大兔子，那么总共就有 $n-m+1$ 只兔子，排列方案数是 $(n-m+1)!$，然而大兔子里面也有 $m!$ 中方法，那么总方法数就是 $(n-m+1)!m!$。这就是捆绑法。

插空法

$n$ 只兔子参观大连市第二十四中学，其中 $m$ 只兔子有着不共戴天之仇，它们一定要不能站在一块。那么有多少种排列方法？

我们先把 $n-m$ 只兔子给排列好，有 $(n-m)!$ 种方法。这些兔子之间有 $(n-m+1)$ 个空（算最左和最右），再把这些不共戴天的兔子放到这些空里，有 $A_{n-m+1}^{m}$ 个方法。总方案数就是 $(n-m)!\times A_{n-m+1}^{m}$。这就是插空法。

插板法

james1 要将 $n$ 个相同的胡萝卜分给 $m$ 只兔子，他秉持雨露均沾的原则，每只兔子至少分到 $1$ 根胡萝卜，有多少种方案？

我们先介绍隔板法（插板法），是指在 $n$ 个元素的 $n-1$ 个空中插入 $k$ 个板，可以把 $n$ 个元素分为 $k+1$ 组。

我们把这 $n$ 个胡萝卜排成 $1$ 行，当中就有 $n-1$ 个空。现在往里面插入 $m-1$ 个板，就可以将胡萝卜分为 $m$ 组，正好可以分给 $m$ 只兔子，而且由于不存在在同一个地方插两个板的情况，所以正好每一只兔子都能至少分到 $1$ 根胡萝卜。那么答案就是 $\dbinom{n-1}{m-1}$。

实际上这个问题相当于求不定方程 $x_1+x_2+\cdots+x_m=n$ 的正整数解的数量。

如果他是个大魔王（不可能，绝对不可能），有的兔子可能 $1$ 根胡萝卜都得不到，那么有多少种方案？

同样的方法，如果允许有兔子分到 $0$ 根胡萝卜，我们只需要再加上 $m$ 根胡萝卜，就相当于刚才的问题了。答案是 $\dbinom{n+m-1}{m-1}=\dbinom{n+m-1}{n}$。

这个问题本质上是要求 $x_1+x_2+\cdots+x_m=n$ 的自然数解的数量。

如果 james1 偏爱一些兔子，要求第 $i$ 个兔子至少分到 $e_i$ 个胡萝卜，那么有多少种分法呢？

类比上一个问题，我们再加上 $\sum e$ 个胡萝卜，答案就是 $\dbinom{n+\sum e - 1}{n}$。

在 $n$ 个数中选 $m$ 个组合，要求任意两个数都不相邻，那么方案数有多少？

$\dbinom{n-m+1}{n}$，因为我们需要插入 $m-1$ 个空。

简单问题

真的只是加法原理和乘法原理而已。

[Luogu P1866] 编号

Portal.

为了尽可能防止负数需要先排序，然后使用乘法原理计算。但如果负数真的出现了，就无解。

#include <bits/stdc++.h>
#define i64 long long

using namespace std;
const i64 MOD = 1000000007;

int n;
int a[55];
i64 ans = 1;

int main(void) {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", a + i);
    sort(a + 1, a + n + 1);
    for (int i = 1, k; i <= n; i++) {
        if ((k = a[i] - (i - 1)) > 0) ans = ans * k % MOD;
        else return puts("0"), 0;
    }
    printf("%d\n", ans);
    return 0;
}

[NOIP2016 提高组] 组合数问题

Portal.

我们直接利用杨辉三角预处理组合数，然后使用二维前缀和计算答案即可。

#include <bits/stdc++.h>
using namespace std;

int C[2005][2005];
int ans[2005][2005];

int main(void) {
    int T, k;
    scanf("%d%d", &T, &k);

    for (int i = 0; i <= 2002; ++i) {
        C[i][0] = 1, C[i][i] = 1;
        for (int j = 1; j <= i; ++j)
            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % k;
    }
    for (int i = 0; i <= 2002; ++i) {
        for (int j = 1; j <= i; ++j)
            ans[i][j] = ans[i - 1][j] + ans[i][j - 1] - ans[i - 1][j - 1] + (C[i][j] == 0);
        ans[i][i + 1] = ans[i][i];
    }

    while (T--) {
        int n, m;
        scanf("%d%d", &n, &m);
        printf("%d\n", ans[n][min(n, m)]);
    }
    return 0;
}

[Luogu P1287] 盒子与球

Portal.

设 $f(i,j)$ 代表考虑前 $i$ 个球，有 $j$ 个盒子的方案数。显然可以是由前 $i-1$ 个球，$j$ 个盒子放在这 $j$ 个盒子中的任意一个，也可以只考虑 $j-1$ 个盒子，只能放在第 $j$ 个盒子，但是这第 $j$ 个盒子的位置可以任意摆放。

#include <bits/stdc++.h>
using namespace std;

int n, r;
int f[15][15];

int main(void) {
    scanf("%d%d", &n, &r);
    f[0][0] = 1;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= min(i, r); ++j)
            f[i][j] = j * (f[i - 1][j] + f[i - 1][j - 1]);
    printf("%d\n", f[n][r]);
    return 0;
}

那么盒子相同呢？这样可以乘 $j$ 的就只有 $f(i-1,j)$ 了，可以做一下 [Luogu P1655] 小朋友的球。

[Luogu P2638] 安全系统

Portal.

不难看出放 01 可以分开计算，最后使用乘法原理组合在一起。而任何一个都可以使用插板法的结论进行计算。

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long u64;

int n, a, b;
u64 C[105][105];

int main(void) {
    C[0][0] = 1;
    for (int i = 1; i <= 100; ++i) {
        C[i][0] = 1;
        for (int j = 1; j <= i; ++j)
            C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
    }
    scanf("%d%d%d", &n, &a, &b);
    u64 ans = 0;
    for (int i = 0; i <= a; ++i)
        for (int j = 0; j <= b; ++j)
            ans += C[n + i - 1][i] * C[n + j - 1][j];
    printf("%llu\n", ans);
    return 0;
}

[Luogu P8557] 炼金术

Portal.

一种金属有 $2^k-1$ 种可能被熔炼出来，然后每一种金属的可能都要乘起来（乘法原理）。

#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;

inline int poww(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = 1ll * res * a % MOD;
        a = 1ll * a * a % MOD;
        b >>= 1;
    }
    return res;
}

int main(void) {
    int n, k; cin >> n >> k;
    cout << poww(poww(2, k) - 1, n) << '\n';
    return 0;
}

[UVA11609] Teams

Portal.

队长有 $n$ 中可能，每一个人当队长剩下的人都有 $2^{n-1}$ 种可能。

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;

int poww(int a, int b) {
	int res = 1;
	while (b) {
		if (b & 1) res = 1ll * res * a % MOD;
		a = 1ll * a * a % MOD;
		b >>= 1;
	}
	return res;
}

int main(void) {
	int T, kase = 0, n;
	scanf("%d", &T);
	while (T--) {
		scanf("%d", &n);
		printf("Case #%d: %d\n", ++kase, 1ll * n * poww(2, n - 1) % MOD);
	}
	return 0;
}

组合工具

计数问题有一些常见的工具可以辅助计算。

组合公式

还记得有关组合数的公式吗？事实上，最重要的内容有名有姓，并且非常有用：

• 吸收恒等式：$\dbinom{r}{k}=\dfrac{r}{k}\dbinom{r-1}{k-1}$，当二项式外有一个无用的系数时，我们可以将它“吸收”进二项式系数。
• 下指标求和（行求和）：$\displaystyle \sum_{i=0}^{n}\binom{n}{i}=2^n$，相当于是二项式定理中 $a=b=1$，它还有变式：
  • $\displaystyle \sum_{i=0}^{n}(-1)^i\binom{n}{i}=0$，这是二项式定理中 $a=1,b=-1$；
  • $\displaystyle \sum_{i=0}^{n}i\times \binom{n}{i}=n2^{n-1}$，因为 $m\times \dbinom{n}{m}=n\times \dbinom{n-1}{m-1}$。
• 上指标求和（列求和）：$\displaystyle \sum_{i=0}^{n}\binom{i}{m}=\binom{n+1}{m+1}$，可以看作是枚举第 $m+1$ 个数的位置 $i+1$。
• 对角线求和：$\displaystyle\sum_{i=0}^{n}\binom{m+i}{i}=\binom{m+n+1}{n}$，反复利用 $C_{n}^{m}=C_{n-1}^{m}+C_{n-1}^{m-1}$ 即可证明。
• 范德蒙德卷积：$\displaystyle \sum_{i=0}^k\binom{n}{i}\binom{m}{k-i}=\binom{n+m}{k}$。从组合意义上很容易证明（枚举 $n$ 和 $m$ 中选的个数），常用于合并组合数，考虑它的推论：
  • $\displaystyle \sum_{i=1}^n\binom{n}{i}\binom{n}{i-1}=\binom{2n}{n-1}$，证明很简单，因为 $\dbinom{n}{i-1}=\dbinom{n}{n-i+1},\dbinom{2n}{n-1}=\dbinom{2n}{n+1}$；
  • $\displaystyle\sum_{i=0}^n\binom{n}{i}^2=\binom{2n}{n}$，证明基本同理；
  • $\displaystyle\sum_{i=0}^m\binom{n}{i}\binom{m}{i}=\binom{n+m}{m}$，这个也是网格图路径计数方案。

N 项式定理

二项式定理也能扩展为 $n$ 项式定理：

$$(x_1+\cdots+x_t)^n=\sum_{n_i\ge 0,n_1+\cdots+n_t}\binom{n}{n_1,\cdots,n_t}x_{1}^{n_1}\cdots x_{t}^{n_t}$$

其中

$$\binom{n}{n_1,\cdots,n_t}=\cfrac{n!}{n_1!\cdots n_t!}$$

Lucas 定理

Lucas 定理是说，对于质数 $p$，有：

$$\binom{n}{m}\bmod p = \binom{\left\lfloor n/p \right\rfloor}{\left\lfloor m/p\right\rfloor}\cdot\binom{n\bmod p}{m\bmod p}\bmod p$$

模板，代码如下：

#include <bits/stdc++.h>
using namespace std;

int n, m, p;
int fac[100005];

void exgcd(int a, int b, int &x, int &y) {
    if (b == 0) return x = 1, y = 0, void();
    exgcd(b, a % b, y, x);
    y -= a / b * x;
}

int inv(int t) {
    int x, y;
    exgcd(t, p, x, y);
    return (x % p + p) % p;
}

int C(int n, int m) {
    if (m > n) return 0;
    if (m == 0 || m == n) return 1;
    return 1ll * fac[n] * inv(fac[m]) % p * inv(fac[n - m]) % p;
}

int Lucas(int n, int m) {
    if (m == 0 || m == n) return 1;
    return 1ll * Lucas(n / p, m / p) * C(n % p, m % p) % p;
}

int main(void) {
    fac[0] = 1;
    int T; cin >> T;
    while (T--) {
        cin >> n >> m >> p;
        for (int i = 1; i <= p; ++i) fac[i] = 1ll * fac[i - 1] * i % p;
        cout << Lucas(n + m, m) << '\n';
    }
    return 0;
}

因此可以发现，Lucas 定理面对的模数不会很大，否则是无法计算的。

而且当模数小的时候，往往需要使用 Lucas 定理。因为 $n$ 可能很大，用公式计算会使得阶乘在模意义下直接变成 $0$。

扩展 Lucas 定理

模板。

容斥原理

容斥原理是非常重要的计数原理，能够对问题的角度进行转化，弱化或者加强问题的限制，从而使问题更加简洁。

引入

容斥原理大家一定不陌生，我们现在要给出 $n$ 个集合的情况。设全集为 $U$，拥有属性 $P_i$ 的元素构成集合 $S_i$，那么：

$$\left|\bigcup_{i=1}^{n}S_i\right|=\sum_{m=1}^n(-1)^{m-1}\sum_{a_i<a_{i+1} }\left|\bigcap_{i=1}^mS_{a_i}\right|$$

集合的交集

可以使用全集 $U$ 减去补集的并集得到。

$$\left|\bigcap_{i=1}^{n}S_i\right|=|U|-\left|\bigcup_{i=1}^n\overline{S_i}\right|$$

子集枚举

子集枚举可以让容斥原理的计算变得非常简便，代码如下：

for (int i = S; i; i = i - 1 & S)

这样 $i$ 枚举的就是 $S$ 的非空子集。

应用

容斥原理最经典的用处是“至少”与“恰好”之间的转化，实际上是一个子集反演的过程。比较抽象，请参考《组合计数进阶》。

经典计数

包括一些经典问题和计数数列。但是限于本文的定位，并不会讲的很深，更深的内容请参考《组合计数进阶》，并先阅读《多项式与生成函数基础》中的生成函数部分。

错排数

是指没有任何元素出现在其有序位置的排列，也就是说不存在 $P_i=i$。

我们使用递推计算这个问题，设 $f(i)$ 为长度为 $i$ 的答案。那么可以前 $i-1$ 个全部排错，只需要第 $i$ 个与前 $i-1$ 个中的任意一个互换即可，方案数为 $(i-1)f_{i-1}$；也可以前面仅有一个没有排错，只需要将这个与 $i$ 互换，方案数为 $(i-1)f_{i-2}$（没错排的可以是任意一个）。

因此：$f_i=(i-1)(f_{i-1}+f_{i-2})$。

斯特林数

分为第一类斯特林数和第二类斯特林数。由于后者更为常用，因此我们先来研究后者。

第二类斯特林数

第二类斯特林数使用 $\begin{Bmatrix}n\\ k\end{Bmatrix}$ 或者 $S(n,k)$ 来表示，意义是将 $1\sim n$ 的整数划分为 $k$ 个不交的集合的方案数。显然 $\begin{Bmatrix}n\\ 0\end{Bmatrix}=[n=0]$。可以采用暴力递推法求解：

$$\begin{Bmatrix}n\\ k\end{Bmatrix}=\begin{Bmatrix}n-1\\ k-1\end{Bmatrix}+k\begin{Bmatrix}n-1\\ k\end{Bmatrix}$$

什么意思呢？将第 $n$ 个元素放入一个新的集合有 $\begin{Bmatrix}n-1\\ k-1\end{Bmatrix}$ 种方案，将第 $n$ 个元素插入原来任意一个集合有 $k\begin{Bmatrix}n-1\\ k\end{Bmatrix}$ 的方案，根据加法原理可得递推式。

可能需要记住一些第二类斯特林数（就比如说，一个出现 $1,7,6,1$ 的问题就很大能与第二类斯特林数有关）：

1
1 1
1 3 1
1 7 6 1
1 15 25 10 1
1 31 90 65 15 1
1 63 301 350 140 21 1
1 127 966 1701 1050 266 28 1
1 255 3025 7770 6951 2646 462 36 1
1 511 9330 34105 42525 22827 5880 750 45 1

第二类斯特林数的通项公式：

$$\begin{Bmatrix}n\\m\end{Bmatrix}=\sum\limits_{i=0}^m\frac{(-1)^{m-i}i^n}{i!(m-i)!}$$

第一类斯特林数

称之为斯特林轮换数，记作 $\begin{bmatrix}n\\ k\end{bmatrix},s(n,k)$，表示将 $1\sim n$ 的整数划分为 $k$ 个互不区分的非空轮换方案数。

一个轮换是指一个首尾相接的环形排列，两个可以通过旋转而互相得到的轮换是等价的。

第一类斯特林数的递推式：

$$\begin{bmatrix}n\\ k\end{bmatrix}=\begin{bmatrix}n-1\\ k-1\end{bmatrix}+(n-1)\begin{bmatrix}n-1\\ k\end{bmatrix}$$

前者是将 $n$ 放在一个单独的轮换中，后者是将其放入一个现有的轮换中。

这个玩意没有实用的通项公式。

卡特兰数

前几项长这样：1 1 2 5 14 42 132，需要记住。它有非常多的含义：

1. $n$ 个节点可构造的不同二叉树个数；
2. $n$ 个数不同的出栈序列个数；
3. ……

常见公式：

$$H_n=\frac{H_{n-1}(4n-2)}{n+1}\\ H_n=\binom{2n}{n}-\binom{2n}{n-1}\\ H_n=\sum_{i=0}^{n-1}H_i\times H_{n-i-1}(n\ge 2)$$

多重集相关问题

我们知道一个多重集 $S$ 可以不满足互异性。设 $S=\{n_1\times a_1\cdots n_k\times a_k\}$ 代表由 $n_i$ 个 $a_i$ 组成的多重集。

多重集的排列数 | 多重组合数

这两个是同一个概念，是要求大小为 $n$，第 $i$ 个数出现次数为 $n_i$ 的多重集 $S$ 的全排列个数，我们要除掉重复的个数，那么 $S$ 的全排列个数等于（其实就是把相同的数除掉了）：

$$\binom{n}{n_1,\dots,n_k}=\frac{n!}{\prod_{i=1}^k n_i!}$$

多重组合数的意义就是先选 $n_1$ 个，再在剩下的选择 $n_2$ 个，以此类推。

数的个数显然就是多重组合数，然后有 $n$ 个位置，总共的序列个数有多重组合数 $s$ 个。设所有数的和为 $sum$，那么平均每一位的值就是 $sum\div n$，然后再乘上基数，全是 $1$ 即可。

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;
typedef unsigned long long u64;

int main(void)
{
    int n; u64 f[15] = {1};
    const u64 one[] = {0, 1, 11, 111, 1111, 11111, 111111, 1111111, 11111111, 111111111, 1111111111, 11111111111, 111111111111};
    for (int i = 1; i <= 12; ++i)
        f[i] = f[i - 1] * i;
    while (scanf("%d", &n) == 1 && n)
    {
        static int cnt[10];
        u64 sum = 0;
        memset(cnt, 0, sizeof(cnt));
        for (int i = 1, x; i <= n; ++i)
            scanf("%d", &x), ++cnt[x], sum += x;
        u64 s = f[n];
        for (int i = 0; i < 10; ++i) s /= f[cnt[i]];
        printf("%llu\n", sum * s * one[n] / n);
    }
    return 0;
}

Problemset

这里的题目都是比较基础的数数题。

简单问题

可以用来巩固基础。

[USACO20FEB] Help Yourself G

好题！似乎没有什么特殊做法，那么考虑计数 DP。设 $f_i$ 代表考虑前 $i$ 条线段的复杂度之和。如果不选第 $i$ 条线段，那么复杂度和是 $f_{i-1}$；如果选第 $i$ 条线段，那么是多少？不好做！加入这一条线段之后可能新增联通块，也可能合并联通块，鬼知道贡献是什么！

换句话说，状态的转移顺序有问题，导致贡献不好计算。我们可以按照线段的左端点从小到大排序之后再进行计算。这样就不可能合并联通块，所以原来的贡献 $f_{i-1}$ 都在；新增联通块是可以的，假设前面与当前线段不交的线段有 $x$ 条（可以使用前缀和统计），那么新增的复杂度就是 $2^x$（就是只选这 $x$ 条线段的子集时，复杂度会增加 $1$）。

#include <bits/stdc++.h>
#define L first
#define R second

using namespace std;
const int MOD = 1000000007;

int n, f[100005], s[200005];
pair<int, int> a[100005];

int poww(int a, int b) {
    int res = 1;
    for (; b; b >>= 1, a = 1ll * a * a % MOD)
        if (b & 1) res = 1ll * res * a % MOD;
    return res;
}

int main(void) {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) 
        scanf("%d%d", &a[i].L, &a[i].R), s[a[i].R]++;
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n * 2; ++i) s[i] += s[i - 1];
    for (int i = 1; i <= n; ++i)
        f[i] = (f[i - 1] * 2 % MOD + poww(2, s[a[i].L - 1])) % MOD;
    printf("%d\n", f[n]);
    return 0;
}

[CF340E] Iahub and Permutations

本质上是一个错排问题，但是其中的 $-1$ 可以有随便填的，加一个转移来处理它！

#include <bits/stdc++.h>
using namespace std;
const int P = 1000000007; 

int n, a[2005], tot1, tot2; // 不能放自身，可以随便放
bool p[2005]; 
int f[2005]; 

int main(void) {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", a + i);
        if (a[i] == i) return puts("0"), 0; 
        if (a[i] != -1) p[a[i]] = true;
        else ++tot1; 
    }
    for (int i = 1; i <= n; ++i)
        if (a[i] == -1 && p[i]) tot1--, tot2++;
    for (int i = f[0] = 1; i <= tot2; ++i) f[0] = 1ll * f[0] * i % P;
    f[1] = 1ll * tot2 * f[0] % P;
    for (int i = 2; i <= tot1; ++i) {
        f[i] = 1ll * (f[i - 1] + f[i - 2]) * (i - 1) % P;
        f[i] = (f[i] + 1ll * tot2 * f[i - 1]) % P;
    }
    return !printf("%d\n", f[tot1]);
}

[AHOI2022] 排列

Portal.

建出置换的有向图，每个环独立，那么 $v$ 就是每个环大小的 LCM。如果 $i,j$ 在一个环里，那么 $f(i,j)=0$。

这个 swap 操作相当于合并了两个环，设第 $i$ 个环的大小为 $a_i$，那么由于 $\sum a_i=n$，因此值不同的 $a_i$ 在 $\sqrt{n}$ 级别。我们只需要暴力枚举两个环的大小，这样的时间复杂度是 $O(n)$ 的。

也就是说，我们需要维护一个集合的 LCM，支持删除两个数并加入一个新的数求出 LCM。将数质因数分解，对于每个质数只保留三个幂次最大的（删除两个数时最坏只会删掉两个最大的），加入的时候暴力统计一下即可。

#include <bits/stdc++.h>
using namespace std;
const int P = 1000000007;
const int N = 500000; 
void add(int &x, int t) { x += t; if (x >= P) x -= P; }

int n; 
int a[500005];
int fa[500005], siz[500005];

int find(int x) {
    if (fa[x] == x) return x;
    return find(fa[x]);
}
void uni(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return;
    if (siz[x] > siz[y]) swap(x, y);
    fa[x] = y; siz[y] += siz[x];
}

int cnt[500005];
int prime[500005], tot, p[500005], inv[500005]; // p: 最小质因子
vector<pair<int, int>> fac[500005]; // fac[i] 保存 i 质因数分解后的结果，first 为底数，second 为幂
vector<int> G[500005]; // G[i] 保存质数 i 为底数的最大幂
vector<pair<int, int>> E[500005]; // E 为临时附加
int A[1005], t, now;

int C[500005];
int get(int v) { // 获取质数 v 的最大幂
    int mx = 1; 
    for (int x : G[v]) ++C[x];
    for (auto [x, k] : E[v]) C[x] += k;
    for (int x : G[v]) if (C[x]) mx = max(mx, x), C[x] = 0; 
    for (auto [x, k] : E[v]) if (C[x]) mx = max(mx, x), C[x] = 0; 
    return mx;
}

void update(int v, int flag) {
    for (auto [x, y] : fac[v]) {
        now = 1ll * now * inv[get(x)] % P;
        E[x].emplace_back(y, flag);
        now = 1ll * now * get(x) % P;
    }
}
void remove(int v) {
    for (auto [x, y] : fac[v]) E[x].clear();
}

int main(void) {
    p[1] = inv[1] = 1;
    for (int i = 2; i <= N; ++i) inv[i] = 1ll * (P - P / i) * inv[P % i] % P;
    for (int i = 2; i <= N; ++i) {
        if (!p[i]) prime[++tot] = i, p[i] = i; 
        for (int j = 1; j <= tot && i * prime[j] <= N; ++j) {
            p[i * prime[j]] = prime[j];
            if (i % prime[j] == 0) break;
        }
    }
    for (int i = 1; i <= N; ++i) {
        int x = i; 
        while (x != 1) {
            int tmp = p[x], v = 1; 
            while (x % tmp == 0) x /= tmp, v *= tmp; 
            fac[i].emplace_back(tmp, v);
        }
    }

    int T; scanf("%d", &T); 
    while (T--) {
        memset(cnt, 0, sizeof cnt); t = 0; 

        scanf("%d", &n); 
        for (int i = 1; i <= n; ++i) scanf("%d", a + i), fa[i] = i, siz[i] = 1;
        for (int i = 1; i <= n; ++i) uni(i, a[i]), G[i].clear();
        
        for (int i = 1; i <= n; ++i) if (find(i) == i) { 
            ++cnt[siz[i]];    
            for (auto [x, y] : fac[siz[i]]) G[x].emplace_back(y);
        }
        for (int i = 1; i <= n; ++i) if (cnt[i]) A[++t] = i; 
        
        now = 1; 
        for (int i = 1; i <= n; ++i) if (G[i].size()) {
            sort(G[i].begin(), G[i].end(), greater<int>());
            while (G[i].size() > 3) G[i].pop_back();
            now = 1ll * now * G[i][0] % P;
        }

        int ans = 0; 
        for (int i = 1; i <= t; ++i) {
            int u = A[i];
            if (cnt[u] > 1) {
                int last = now;
                update(u, -1); update(u, -1); update(u + u, 1);
                add(ans, 1ll * cnt[u] * (cnt[u] - 1) % P * u % P * u % P * now % P);
                remove(u); remove(u + u); 
                now = last;
            }
            for (int j = i + 1; j <= t; ++j) {
                int last = now, v = A[j];
                update(u, -1); update(v, -1); update(u + v, 1);
                add(ans, 2ll * cnt[u] * cnt[v] % P * u % P * v % P * now % P); 
                remove(u); remove(v); remove(u + v); 
                now = last; 
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

[CF348D] Turtles

Portal.

只有一只乌龟的话是经典问题，现在考虑两条路径什么时候有交。

只能是一只乌龟从 $(1,2)$ 走到 $(n-1,m)$，另一只乌龟从 $(2,1)$ 走到 $(n,m-1)$。如果一只乌龟从 $(1,2)$ 走到 $(n,m-1)$，另一只乌龟从 $(2,1)$ 走到 $(n-1,m)$，那么这样路径是会有交的。

但是发现前者自身也有可能有路径交！比如说中途在一个点路径相交。我们把这个点之后的路径互换，发现都可以对应到第二种的走法。这样只需要用前者减去后者即可。

#include <bits/stdc++.h>
using namespace std;
const int P = 1000000007;

int n, m;
char s[3005][3005];
int f[3005][3005]; 

int dp(int x, int y, int n, int m) {
    memset(f, 0, sizeof f); 
    for (int i = x; i <= n; ++i)
        for (int j = y; j <= m; ++j) if (s[i][j] != '#') {
            if (i == x && j == y) f[i][j] = 1; 
            else f[i][j] = (f[i - 1][j] + f[i][j - 1]) % P; 
        } 
    return f[n][m]; 
}

int main(void) {
    scanf("%d%d", &n, &m); f[1][1] = 1; 
    for (int i = 1; i <= n; ++i) scanf("%s", s[i] + 1); 
    printf("%d\n", ((1ll * dp(1, 2, n - 1, m) * dp(2, 1, n, m - 1) - 1ll * dp(1, 2, n, m - 1) * dp(2, 1, n - 1, m)) % P + P) % P); 
    return 0;
}

实际上本题是 LGV 引理的一个应用，相关内容在《组合计数进阶》有介绍。由于本题只有两只乌龟，因此可以比较方便的用容斥原理理解。

计数问题

借助动态规划算法的多阶段决策，可以高效的解决计数问题。

[HAOI2008] 硬币购物

Portal.

如果每一种硬币都有无限多，那么这就成了个完全背包，直接做就可以，记为 $f(s)$。

接下来考虑性质。利用补集思想，我们可以用 $f(s)$ 减去至少有一个超过。也就是 $f(s-(d_1+1)\times c_1)$，以此类推。使用容斥原理计算即可。

#include <iostream>
#include <cstdio>

using namespace std;
typedef long long i64;
const int M = 100000;

int c1, c2, c3, c4, q;
i64 f[M + 5];
inline i64 g(i64 x) { return x < 0 ? 0 : f[x]; }

int main(void) {
    cin >> c1 >> c2 >> c3 >> c4 >> q;
    f[0] = 1;
    for (int i = c1; i <= M; ++i) f[i] += f[i - c1];
    for (int i = c2; i <= M; ++i) f[i] += f[i - c2];
    for (int i = c3; i <= M; ++i) f[i] += f[i - c3];
    for (int i = c4; i <= M; ++i) f[i] += f[i - c4];
    while (q--) {
        int d1, d2, d3, d4, s;
        cin >> d1 >> d2 >> d3 >> d4 >> s;
        d1 = (d1 + 1) * c1, d2 = (d2 + 1) * c2, d3 = (d3 + 1) * c3, d4 = (d4 + 1) * c4;
        cout << g(s) - g(s - d1) - g(s - d2) - g(s - d3) - g(s - d4) +
        g(s - d1 - d2) + g(s - d1 - d3) + g(s - d1 - d4) + g(s - d2 - d3)
        + g(s - d2 - d4) + g(s - d3 - d4) - g(s - d1 - d2 - d3) - g(s - d1 - d3 - d4)
        - g(s - d1 - d2 - d4) - g(s - d2 - d3 - d4) + g(s - d1 - d2 - d3 - d4) << '\n'; 
    }
    return 0;
}