抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

组合计数进阶

更新于 2022年12月23日

8k 字

41 分钟

次浏览

高阶的计数问题更为困难。在阅读本文之前，请确保你对生成函数和多项式有一定的了解。

常见构造手段

计数问题有一些常有的求解手段。在研究更多内容前，我们先了解一下这些方法。

构造双射

不同的两个组合类中的组合对象可以一一对应，这样对两个组合类进行计数是等价的。

有时同一组合类中的组合对象可以建立一一对应（或多个为一组），我们只需抽取每对（或每组）中的一个进行计数，再乘上或除以相应的大小即可。

增量法

计数问题的常见手段，莫队的扩展也是这一思想。就是从 (n,m)(n,m) 扩展到 (n+1,m+1)(n+1,m+1)，考虑贡献增加的量。

有时问题无法直接处理，只能考虑增量法。

差分法

比如说查询恰好为 xx 的方案数，可以用 ≤x\le x 的方案数和 ≤x−1\le x-1 的方案数相减得到。

权值的贡献

一般我们会从权值的角度去考虑，可以从权值下标的顺序进行考虑，也可以从每一个权值对式子的贡献考虑。

算两次

如维度的变换（枚举下标、权值）、贡献的计算（直接或增量计算）。选择合适的角度后，再使用加法原理和乘法原理等计数方法解决问题。

有时也可以考虑更换计数顺序，或者用两种不同的方式计算同一个量，从而建立相等关系。

Prufer 序列

这是一种将无根树转化为一个唯一的整数序列的表示方法（前提是，这个树应该至少有两个节点）。

构造

Prufer 序列可以将一个 nn 个节点的无根树用 [1,n][1,n] 中的 n−2n-2 个整数表示，常用于组合计数。

建立时，每次选择一个编号最小的叶子删除它，然后在序列中记录下它连接到的那个节点，重复 n−2n-2 次算法结束。可以使用如下方法进行 O(n)O(n) 构造：

  1. 自增 pp 使其指向编号最小的叶节点，将其删除；
  2. 检查是否产生新的叶节点，如果产生且编号比 pp 小，则立即删除，重复此操作；
  3. pp 自增，回到步骤 11 直到 Prufer 序列构造完毕。

还原

根据 Prufer 序列也可以还原树。方法是一样的，注意先将 prufer[n−1]prufer[n-1] 设为 nn，并将赋值的内容反过来即可。具体见代码。

模板，代码如下：

查看代码 
#include <bits/stdc++.h>
using namespace std;
typedef long long i64;
const int N = 5000000;

int n, m;
i64 ans = 0;
int fa[N + 5], du[N + 5];
int p[N + 5];

void treeToPrufer(void) {
    for (int i = 1; i < n; ++i) scanf("%d", fa + i), ++du[fa[i]];
    for (int i = 1, now = 1; i < n; ++i, ++now) {
        while (du[now]) ++now; p[i] = fa[now];
        while (i < n - 2 && --du[p[i]] == 0 && p[i] < now) p[i + 1] = fa[p[i]], ++i;
    }
    for (int i = 1; i < n - 1; ++i) ans ^= 1ll * i * p[i];
}

void pruferToTree(void) {
    for (int i = 1; i < n - 1; ++i) scanf("%d", p + i), ++du[p[i]]; 
    p[n - 1] = n;
    for (int i = 1, now = 1; i < n; ++i, ++now) {
        while (du[now]) ++now; fa[now] = p[i];
        while (i < n - 1 && --du[p[i]] == 0 && p[i] < now) fa[p[i]] = p[i + 1], ++i;
    }
    for (int i = 1; i < n; ++i) ans ^= 1ll * i * fa[i];
}

int main(void) {
    scanf("%d%d", &n, &m);
    if (m == 1) treeToPrufer();
    else pruferToTree();
    printf("%lld\n", ans);
    return 0;
}

性质

每个节点在 Prufer 序列中出现次数是其度数减 11。

完全图有 nn−2n^{n-2} 棵生成树，因为每一个 Prufer 序列都对应一棵树。这就是 Cayley 公式。

容斥原理与反演

反演是指两个函数（数列）之间的双射（比如前缀和和差分）。

子集反演

子集反演是针对集合交并的容斥，可以在恰好是某个集合和至多/至少是这个集合反演。

我们先来看与至多是这个集合的反演。现在有其元素满足某种条件的集合 AA。定义 f(S)f(S) 代表 S=AS=A 时的答案，g(S)g(S) 代表 S⊆AS\subseteq A 时的答案。

钦定选了 SS 这个集合中的子集 TT，有 g(S)=∑T⊆Sf(T)g(S)=\sum_{T\subseteq S}f(T)，这时有 f(S)=∑T⊆S(−1)∣S∣−∣T∣g(T)f(S)=\sum_{T\subseteq S}(-1)^{|S|-|T|}g(T)。使用容斥原理不难感性理解。

类似的，如果 f(S)f(S) 代表 S=AS=A 时的答案，g(S)g(S) 表示 A⊆SA\subseteq S 时的答案，有 g(S)=∑S⊆Tf(T)g(S)=\sum_{S\subseteq T}f(T)，反演得 f(S)=∑S⊆T(−1)∣T∣−∣S∣g(T)f(S)=\sum_{S\subseteq T}(-1)^{|T|-|S|}g(T)。

实际上这是容斥原理的代数形式，它是我们用容斥原理解决问题的基础。因为在钦定时，一个“有两个元素满足条件”的东西会在“至少有一个元素满足条件”的东西计算时计算两次，也就因此成了一个子集反演的形式。

二项式反演

二项式反演是容斥原理的代数形式。假设全集 U={S1,S−2,⋯ ,Sn−1,Sn}U=\{S_1, S-2, \cdots, S_{n-1}, S_n\}，且满足其中任意 ii 个集合的并集、交集大小都相等。g(x)g(x) 是其中任意 xx 个集合的交集的大小，f(x)f(x) 是任意 xx 个集合的补集的交集的大小。特别地，g(0)=f(0)=∣U∣g(0)=f(0)=|U|。

我们有：

g(n)= ∣S1∩S2∩⋯Sn−1∩Sn∣= ∣U∣−∣S1‾∪⋯∪Sn‾∣= ∣U∣−∑m=1n(−1)m−1∑ai<ai+1∣Sa1‾∩⋯∩Sam‾∣= ∣U∣−∑i=1n(−1)i−1(ni)f(i)= ∑i=0n(−1)i(ni)f(i)\begin{aligned} g(n)=\ &|S_1\cap S_2\cap\cdots S_{n-1}\cap S_n|\\ =\ &|U|-|\overline{S_1}\cup\cdots\cup\overline{S_n}|\\ =\ &|U|-\sum_{m=1}^n(-1)^{m-1}\sum_{a_i <a_{i+1}}|\overline{S_{a_1}}\cap\cdots\cap\overline{S_{a_m}}|\\ =\ & |U|-\sum_{i=1}^n(-1)^{i-1}\binom{n}{i}f(i)\\ =\ &\sum_{i=0}^n(-1)^{i}\binom{n}{i}f(i) \end{aligned}

g(n)=∑i=0n(−1)i(ni)f(i)  ⟺  f(n)=∑i=0n(−1)i(ni)g(i)\begin{aligned} &g(n)=\sum_{i=0}^n(-1)^{i}\binom{n}{i}f(i)\\ \iff& f(n)=\sum_{i=0}^n(-1)^{i}\binom{n}{i}g(i) \end{aligned}

如果令 f(i)′=(−1)if(i)f(i)'=(-1)^i f(i)，那么可以得到另一个形式（这个形式更为常用，因为大多数题并不会凑出一个 −1-1，以下式子中的 f,gf,g 均没有特定的含义）：

g(n)=∑i=0n(ni)f(i)  ⟺  f(n)=∑i=0n(−1)n−i(ni)g(i)\begin{aligned} &g(n)=\sum_{i=0}^n\binom{n}{i}f(i)\\ \iff& f(n)=\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}g(i) \end{aligned}

同时还有一种上指标的二项式反演：

g(n)=∑i=nN(−1)i(in)f(i)  ⟺  f(n)=∑i=nN(−1)i(in)g(i)\begin{aligned} &g(n)=\sum_{i=n}^N(-1)^i\binom{i}{n}f(i)\\ \iff& f(n)=\sum_{i=n}^N(-1)^i\binom{i}{n}g(i) \end{aligned}

g(n)=∑i=nN(in)f(i)  ⟺  f(n)=∑i=nN(−1)i−n(in)g(i)\begin{aligned} &g(n)=\sum_{i=n}^N\binom{i}{n}f(i)\\ \iff& f(n)=\sum_{i=n}^N(-1)^{i-n}\binom{i}{n}g(i) \end{aligned}

具体应用请见 Problemset。

斐波那契数

卡特兰数

格路计数问题

在平面直角坐标系中，横坐标和纵坐标都是整数的点称为格点，格路是指只经过格点的路径，格路的长度是其经过格点所走的步数。

看似简单的问题实则有非常多的变种，这里仅看几种简单的。

自由路问题

从 (0,0)(0,0) 到 (n,m)(n,m)，只能向上走或者向右走的格路称为自由路，不难看出方案数为 (n+mm)\dbinom{n+m}{m}。

斯特林数

其它计数数列

贝尔数

伯努利数

分拆数

欧拉数

Problemset

知识点比较杂，可能需要经常回顾。

Prufer 序列

基本上只将树转化为 Prufer，应用于计数。

[HNOI2004] 树的计数

Portal.

Prufer 序列可以任意构造，而一个数会在 Prufer 序列中重复出现 di−1d_i-1 次，所以实际上这是多重集的排列数。另外，注意判无解。

查看代码 
#include <iostream>
#include <cstdio>

using namespace std;
typedef long long i64;

int n, s;
int d[155];
int c1[155], c2[155];

void divide(int x, int *c) {
    for (int i = 2; i * i <= x; ++i)
        while (x % i == 0) ++c[i], x /= i;
    if (x > 1) ++c[x];
}

int main(void) {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", d + i), s += d[i];
    if (n * 2 != s + 2) return !puts("0");
    if (n == 1) return !puts(d[1] == 0 ? "1" : "0");
    for (int i = 1; i < n - 1; ++i) divide(i, c1);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j < d[i]; ++j) divide(j, c2);
        if (d[i] == 0) return !puts("0");
    }
    i64 ans = 1;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= c1[i] - c2[i]; ++j)
            ans *= i;
    printf("%lld\n", ans);
    return 0;
}

[CF156D] Clues

Portal.

只剩下 k−2k-2 个点的 Prufer 序列来填，而已经填了的连通块可以根据乘法原理随便选来代表将此联通块抽象成一个点来根据 Prufer 序列构建树。

查看代码 
#include <bits/stdc++.h>
using namespace std;
int P; 

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

int n, m;
int col[100005], cnt, siz[100005];  
vector<int> G[100005]; 

void dfs(int x) {
    ++siz[col[x] = cnt];
    for (int y : G[x]) if (!col[y]) dfs(y); 
}

int main(void) {
    scanf("%d%d%d", &n, &m, &P); 
    while (m--) {
        int u, v; scanf("%d%d", &u, &v); 
        G[u].emplace_back(v); G[v].emplace_back(u); 
    }
    for (int i = 1; i <= n; ++i) if (!col[i]) ++cnt, dfs(i); 
    if (cnt == 1) return printf("%d\n", 1 % P), 0; 
    int ans = poww(n, cnt - 2); 
    for (int i = 1; i <= cnt; ++i) ans = 1ll * ans * siz[i] % P; 
    printf("%d\n", ans); 
    return 0;
}

[CF1762E] Tree Sum

Portal.

设连接 ii 的边权为 did_i，而每条边对 ∏di\prod d_i 的贡献为 11，然而 nn 为奇数时 ∏di=−1\prod d_i=-1 永远不可能满足，因此 nn 为奇数时无解。

如果 nn 为偶数且树的形态固定，那么参考 Prufer 序列的构造方式，从叶子开始赋予边权，那么方式一定是唯一的！也就是说，对于给定的树的形态只有一种方式。

这样的话，一条边 (u,v)(u,v) 的权值为 11 的充要条件是：断掉这条边之后两个连通块大小均为偶数。因为这样两个连通块都满足条件了，这条边填 11 即可。

考虑逐边计算贡献，枚举 11 所在的连通块大小 ii，这样 nn 所对应的连通块大小便为 n−in-i。

  • 此时这条边的边权为 (−1)i(-1)^i。
  • 剩下 nn 个点中随便扔，方案数为 (n−2i−1)\binom{n-2}{i-1}。
  • 两块随便制造无根树，根据 Cayley 公式计算即可。
  • 随便找两个点连接。
查看代码 
#include <bits/stdc++.h>
using namespace std;
const int P = 998244353; 

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

int n; 
int fac[500005], ifac[500005]; 

int C(int n, int m) {
    return 1ll * fac[n] * ifac[m] % P * ifac[n - m] % P; 
}

int f(int n) {
    if (n == 1) return 1; 
    return poww(n, n - 2); 
}

int main(void) {
    scanf("%d", &n); 
    if (n & 1) return puts("0"), 0; 
    for (int i = fac[0] = 1; i <= n; ++i) fac[i] = 1ll * fac[i - 1] * i % P; 
    ifac[n] = poww(fac[n], P - 2); 
    for (int i = n - 1; i >= 0; --i) ifac[i] = 1ll * ifac[i + 1] * (i + 1) % P;
    int ans = 0; 
    for (int i = 1; i < n; ++i)
        ans = (ans + (i & 1 ? -1ll : 1ll) * i * (n - i) % P * C(n - 2, i - 1) % P * f(i) % P * f(n - i) % P) % P; 
    printf("%d\n", (ans % P + P) % P);  
    return 0;
}

格路计数问题

其变种很多，感兴趣的读者可以自行研究。

[CF559C] Gerald and Giant Chess

Portal.

设 f(i)f(i) 为走到第 ii 个点的方案数，然后直接转移即可。

查看代码 
#include <iostream>
#include <cstdio>
#include <algorithm>
#define X first 
#define Y second

using namespace std;
typedef long long i64;
const int MOD = 1000000007;

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

int h, w, n;
pair<int, int> a[2005]; 
i64 fac[200005], f[2005];
int C(int n, int m) {
    if (n < 0 || m < 0 || n < m) return 0;
    return fac[n] * poww(fac[m] * fac[n - m], MOD - 2) % MOD;
}

int main(void) {
    scanf("%d%d%d", &h, &w, &n); fac[0] = 1;
    for (int i = 1; i <= 200000; ++i) fac[i] = fac[i - 1] * i % MOD;
    for (int i = 1; i <= n; ++i) scanf("%d%d", &a[i].X, &a[i].Y);
    sort(a + 1, a + n + 1); a[n + 1] = {h, w};
    for (int i = 1; i <= n + 1; ++i) {
        f[i] = C(a[i].X + a[i].Y - 2, a[i].X - 1);
        for (int j = 1; j < i; ++j)
            f[i] = (f[i] - f[j] * C(a[i].X - a[j].X + a[i].Y - a[j].Y, a[i].X - a[j].X)) % MOD;
        f[i] = (f[i] + MOD) % MOD;
    }
    printf("%lld\n", f[n + 1]);
    return 0;
}

[JLOI2015] 骗我呢

Portal.

说起来，毕业之后 B 君也就见过 R 君两面而已。
R 君有一个 n×mn \times m 的数组 xi,j(1≤i≤n;1≤j≤m)x_{i,j}(1 \le i \le n; 1 \le j \le m)。
对于 1≤i≤n;1≤j≤m1 \le i \le n; 1 \le j \le m，满足0≤xi,j≤m0 \le x_{i,j} \le m。求 可能的数组xi,jx_{i,j} 的解数。
B 君觉得限制太宽松，还要求对于 1≤i≤n;1≤j<m1 \le i \le n; 1 \le j<m，满足 xi,j<xi,j+1x_{i,j} <x_{i,j+1}，对于 1<i≤n;1≤j<m1 <i \le n; 1 \le j<m，满足 xi,j<xi−1,j+1x_{i,j} <x_{i-1,j+1}。
B 君认为 R 君可以直接 pwn 掉这个题。
R 君说：「黑的实在逼真 =.=，你起码把解数模 109+710^9+7 吧。」B 君觉得 R 君说的有道理，于是想让你求解数模 109+710^9+7 的结果。

对于 100%100\% 的数据，1≤m,n≤1061 \leq m, n \leq 10^6。

写出暴力 DP 转移方程后发现这其实是个格路计数问题，起点是 (0,0)(0,0)，终点是 (n+m+1,n)(n+m+1,n)，不能碰到 y=x+1,y=x−m−2y=x+1, y=x-m-2。

我们将终点 TT 做关于两条直线的对称，得到 T1,T2T1,T2（翻转之后的路径也是可以翻转的）。这样我们只需要减去经过两条直线的方案数，而且是最后经过的（否则先经过一条直线再经过另一条的这种会算重，要及时减去）。

查看代码 
#include <iostream>
#include <cstdio>

using namespace std;
const int MOD = 1000000007;
const int N = 3000000;

int n, m;
int fac[N + 5];

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 C(int n, int m) {
    if (n < m || n < 0 || m < 0) return 0;
    return 1ll * fac[n] * poww(1ll * fac[m] * fac[n - m] % MOD, MOD - 2) % MOD;
}
void trans(int &x, int &y, int k) {
    swap(x, y);
    x -= k; y += k;
}

int main(void) {
    scanf("%d%d", &n, &m); fac[0] = 1;
    for (int i = 1; i <= N; ++i) fac[i] = 1ll * fac[i - 1] * i % MOD;
    int ans, x, y;
    for (x = n + m + 1, y = n, ans = C(x + y, y); x >= 0 && y >= 0;) {
        trans(x, y, 1);
        ans = (ans - C(x + y, y)) % MOD;
        trans(x, y, -m - 2);
        ans = (ans + C(x + y, y)) % MOD;
    }
    for (x = n + m + 1, y = n; x >= 0 && y >= 0;) {
        trans(x, y, - m - 2);
        ans = (ans - C(x + y, y)) % MOD;
        trans(x, y, 1);
        ans = (ans + C(x + y, y)) % MOD;
    }
    printf("%d\n", (ans % MOD + MOD) % MOD);
    return 0;
}

组合反演与容斥原理

包括二项式反演和子集反演，和一些容斥原理难题。

[Luogu P4859] 已经没有什么好害怕的了

Portal.

给定长度为 nn 的两个序列 A,BA,B，要求两两配对使得 a>ba>b 的对数减去 a<ba<b 的对数等于 kk 的情况个数，对 109+910^9+9 取模，保证没有重复数字，n≤2000n\le 2000。

将 A,BA,B 排序。设 a>ba>b 的数量为 xx，那么 x=n+k2x=\cfrac{n+k}{2}（接下来的 kk 均指 xx），令 fi,jf_{i,j} 代表考虑前 ii 个 aa 中选了 jj 组 a>ba>b 的方案数，易得 f0,0=1,fi,j=fi−1,j+fi−1,j−1∗(l[i]−j+1)f_{0,0}=1,f_{i,j}=f_{i-1,j}+f_{i-1,j-1}*(l[i]-j+1)（l[i]l[i] 代表 BB 中最后一个可以选的）。

设 g(i)g(i) 代表满足 a>ba>b 的组数 ≥i\ge i 的方案数，而 f(i)f(i) 代表恰好。显然 gi=fn,i×(n−i)!, g(k)=∑i=kn(ik)f(i)g_i=f_{n,i}\times (n-i)!,\ g(k)=\sum_{i=k}^{n}\binom{i}{k}f(i)（在 ii 中选择 kk 个作为“至少”所要求的内容），使用二项式反演即可求出 f(k)f(k)。

查看代码 
#include <bits/stdc++.h>
using namespace std;
typedef long long i64;
const int MOD = 1000000009;

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

int n, k;
int a[2005], b[2005], l[2005];
i64 f[2005][2005], g[2005], fac[2005];
int C(int n, int m) {
    return fac[n] * poww(fac[m] * fac[n - m], MOD - 2) % MOD; 
}

int main(void) {
    scanf("%d%d", &n, &k); k = (n + k) / 2; fac[0] = 1;
    for (int i = 1; i <= 2002; ++i) fac[i] = fac[i - 1] * i % MOD;
    for (int i = 1; i <= n; ++i) scanf("%d", a + i);
    for (int i = 1; i <= n; ++i) scanf("%d", b + i);
    sort(a + 1, a + n + 1); sort(b + 1, b + n + 1); f[0][0] = 1;
    for (int i = 1, p = 0; i <= n; ++i) {
        while (p < n && b[p + 1] < a[i]) ++p;
        l[i] = p;
    }
    for (int i = 1; i <= n; ++i) {
        f[i][0] = f[i-1][0];
        for (int j = 1; j <= i; ++j)
            f[i][j] = (f[i-1][j] + f[i-1][j-1] * max(0, l[i] - j + 1)) % MOD;
    }
    for (int i = 0; i <= n; ++i) g[i] = f[n][i] * fac[n - i] % MOD;
    int ans = 0;
    for (int i = k; i <= n; ++i)
        ans = (ans + C(i, k) * g[i] * (i - k & 1 ? -1 : 1)) % MOD;
    printf("%d\n", (ans % MOD + MOD) % MOD);
    return 0;
}

[NOI Online #2 提高组] 游戏

Portal.

设 g(n)g(n) 代表恰好有 nn 个非平局，f(n)f(n) 代表至少有 nn 个非平局（可以通过树形背包求出），两者是一个二项式反演的形式。

查看代码 
#include <bits/stdc++.h>
using namespace std;
typedef long long i64;
const int MOD = 998244353;

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

int n, a[5005], fac[5005], ifac[5005];
int siz[5005], sz[5005], g[5005], f[5005][5005]; // f: 至少有 i 个非平局
vector<int> G[5005];

i64 C(int n, int m) {
    return 1ll * fac[n] * ifac[m] % MOD * ifac[n - m] % MOD;
}

void dfs(int x, int fa) {
    siz[x] = 1; sz[x] = a[x]; f[x][0] = 1; 
    for (auto y : G[x]) if (y != fa) {
        dfs(y, x);
        for (int k = 0; k <= siz[x] + siz[y]; ++k) g[k] = 0;
        for (int i = 0; i <= min(siz[x], n / 2); ++i) if (f[x][i])
            for (int j = 0; j <= min(siz[y], n / 2); ++j) if (f[y][j])
                g[i + j] = (g[i + j] + 1ll * f[x][i] * f[y][j] % MOD) % MOD;
        for (int k = 0; k <= siz[x] + siz[y]; ++k) f[x][k] = g[k];
        siz[x] += siz[y]; sz[x] += sz[y];
    }
    for (int i = min(sz[x],  siz[x] - sz[x]); i >= 1; --i) 
        f[x][i] = (f[x][i] + 1ll * f[x][i - 1] * ((a[x] ? siz[x] - sz[x] : sz[x]) - (i - 1))) % MOD;
}

int main(void) {
    scanf("%d", &n); fac[0] = ifac[0] = 1;
    for (int i = 1; i <= n; ++i) {
        scanf("%1d", a + i);
        fac[i] = 1ll * fac[i - 1] * i % MOD; 
        ifac[i] = poww(fac[i], MOD - 2);
    }
    for (int i = 1; i < n; ++i) {
        int u, v; scanf("%d%d", &u, &v);
        G[u].emplace_back(v); G[v].emplace_back(u);
    }
    dfs(1, 0);
    for (int i = 0; i <= n / 2; ++i) 
        f[1][i] = 1ll * f[1][i] * fac[n / 2 - i] % MOD; // 除平局外，剩下的随便
    for (int i = 0; i <= n / 2; ++i) {
        i64 res = 0;
        for (int j = i; j <= n / 2; ++j)
            res = (res + (j - i & 1 ? -1 : 1) * C(j, i) * f[1][j]) % MOD;
        printf("%lld\n", (res % MOD + MOD) % MOD);
    }
    return 0;
}

[ZJOI2016] 小星星

Portal.

给定一张 nn 个点的无向图和一棵 nn 个节点的树。你可以给这棵树重编号，问有多少种方式使得这棵树是原图的生成树。n≤17n\le 17。

想的暴力点，设 fi,j,Sf_{i,j,S} 代表考虑 ii 的子树，ii 的编号为 jj，子树内的集合编号集合状压后为 SS 的方案数。但是还得枚举子集，乘一个 O(3n)O(3^n) 受不了！

如果我们能求出允许重复的答案也可以。定义 f(S)f(S) 代表 SS 没有重复时的方案数，而 g(S)g(S) 代表 SS 中每个元素至少用一次。这样求出 gg 之后直接用子集反演碾过去即可。

设 fi,j,Sf_{i,j,S} 代表点 ii 代表点 jj，子树内点只能使用 SS 内的作为映射，但是无需不重复。

有：

fi,j,S=∏y∈son(x)(∑k∈S,(j,k)∈Efy,k,S)f_{i,j,S}=\prod_{y\in son(x)}\left(\sum_{k\in S,(j,k)\in E}f_{y,k,S}\right)

时间复杂度降至 O(2nn3)O(2^n n^3)。

查看代码 
#include <bits/stdc++.h>
using namespace std;
typedef long long i64; 

int n, m, S, v[20], tot; 
int E[20][20]; i64 f[20][20]; 
vector<int> G[20];

void dfs(int x, int fa) {
    for (int i = 1; i <= tot; ++i) f[x][i] = 1; 
    for (int y : G[x]) if (y != fa) {
        dfs(y, x); 
        for (int i = 1; i <= tot; ++i) { // f[x][i]
            i64 tmp = 0; 
            for (int j = 1; j <= tot; ++j) if (E[v[i]][v[j]]) tmp += f[y][j]; 
            f[x][i] *= tmp; 
        }
    }
}

int main(void) {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; ++i) {
        int u, v; scanf("%d%d", &u, &v);
        E[u][v] = E[v][u] = 1; 
    }
    for (int i = 1; i < n; ++i) {
        int u, v; scanf("%d%d", &u, &v); 
        G[u].emplace_back(v); G[v].emplace_back(u); 
    }
    i64 ans = 0; 
    for (int S = 0; S < 1 << n; ++S) {
        tot = 0; 
        for (int i = 0; i < n; ++i) if (S >> i & 1) v[++tot] = i + 1; 
        dfs(1, 0); 
        i64 g = 0; 
        for (int i = 1; i <= tot; ++i) g += f[1][i]; 
        ans += (n - tot & 1) ? -g : g;
    }
    printf("%lld\n", ans); 
    return 0;
}

[ZJOI2022] 树

Portal.

开 幕 雷 击。

数数题优先考虑 DP。转移只能对每个点在两棵树上的父亲进行决策，这样 DP 状态只能记录可行的决策点个数，也就是可以作为父亲的点的个数。这样就要钦定剩余节点为叶子节点。

设 f(S)f(S) 代表第一棵树的叶子集合恰好为 SS，g(T)g(T) 代表第二棵子树的叶子集合恰好为 TT。但是不好搞！考虑子集反演，设 f′(S′)f'(S') 代表钦定了第一棵树的叶子节点至多为 S′S'，g′(T′)g'(T') 同理，则：

Ans=∑S∩T=∅,S∪T={1,2,⋯ ,n}f(S)g(T)=∑S∩T=∅,S∪T={1,2,⋯ ,n}∑S′⊆S,T′⊆Tf′(S′)g′(T′)(−1)∣S∣−∣S′∣+∣T∣−∣T′∣=∑S′∩T′=∅f′(S′)g′(T′)(−1)n−∣S′∣−∣T′∣2n−∣S′∣−∣T′∣=∑S′∩T′=∅f′(S′)g′(T′)(−2)n−∣S′∣−∣T′∣\begin{aligned} Ans&=\sum_{S\cap T=\varnothing,S\cup T=\{1,2,\cdots,n\}}f(S)g(T)\\&=\sum_{S\cap T=\varnothing,S\cup T=\{1,2,\cdots,n\}}\sum_{S'\subseteq S,T'\subseteq T}f'(S')g'(T')(-1)^{|S|-|S'|+|T|-|T'|} \\&=\sum_{S'\cap T'=\varnothing}f'(S')g'(T')(-1)^{n-|S'|-|T'|}2^{n-|S'|-|T'|}\\&=\sum_{S'\cap T'=\varnothing}f'(S')g'(T')(-2)^{n-|S'|-|T'|} \end{aligned}

相当于钦定了 S′,T′S',T' 作为可选做父亲的集合（选择一个叶子变成父亲），这样设 fi,j,kf_{i,j,k} 代表考虑到第 ii 个节点，∣{1,⋯ ,i}∩S′∣=j,∣{i+1⋯n}∩T′∣=k|\{1,\cdots,i\}\cap S'|=j,|\{i+1\cdots n\}\cap T'|=k 的方案数。在第一棵子树当中有 jj 中选择父亲的方法，第二棵树中有 kk 种，总共 j×kj\times k 种。

fi−1,j,kf_{i-1,j,k} 可以转移到如下状态：

  • ii 本来属于 S′S'，可以转移到 fi,j+1,kf_{i,j+1,k}；
  • ii 本来属于 T′T'，转移到 fi,j,k−1f_{i,j,k-1}；
  • 两个都不属于，转移到 fi,j,kf_{i,j,k}，容斥系数为 −2-2。

好像有人在考场上直接猜出了容斥系数，神秘的。

初始时 f1,1,k=1f_{1,1,k}=1，统计 k=1k=1 时的答案即可（SS 确定 TT 自然也确定了）。

查看代码 
#include <bits/stdc++.h>
using namespace std;

int n;
int f[505][505][505], P;

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

组合综合

非常有意思！

[LNOI2022] 盒

Portal.

发现 wiw_i 会被使用 ∑∣∑j=1ibj−∑j=1iaj∣\sum |\sum_{j=1}^i b_j-\sum_{j=1}^i a_j| 次。枚举 j=∑k=1ibkj=\sum_{k=1}^i b_k，将 aa 转化为其前缀和，合法的 i,ji,j 的出现条件是前 ii 个数和为 jj，后 n−in-i 个数和为 S−jS-j，于是直接插板可以得到总贡献：

∑i=1n−1wi∑j=0S∣j−ai∣(j+i−1i−1)(S−j+n−i−1n−i−1)\sum_{i=1}^{n-1}w_i\sum_{j=0}^S |j-a_i|\binom{j+i-1}{i-1}\binom{S-j+n-i-1}{n-i-1}

这样的时间复杂度是 O(nS)O(nS) 的。考虑拆绝对值，大概像这样：

∑i=1n−1wi∑j=0S(j−ai)(j+i−1i−1)(S−j+n−i−1n−i−1)+2∑i=1n−1wi∑j=0ai(ai−j)(j+i−1i−1)(S−j+n−i−1n−i−1)\sum_{i=1}^{n-1}w_i\sum_{j=0}^S (j-a_i)\binom{j+i-1}{i-1}\binom{S-j+n-i-1}{n-i-1}+2\sum_{i=1}^{n-1}w_i\sum_{j=0}^{a_i} (a_i-j)\binom{j+i-1}{i-1}\binom{S-j+n-i-1}{n-i-1}

这样让 jj 从 00 开始枚举的目的是让接下来好算。后面的式子显然条件更强，因此以后面那个为例。由于出现减法不好搞，因此拆掉：

∑j=0aiai(j+i−1i−1)(S−j+n−i−1n−i−1)−∑j=0aij(j+i−1i−1)(S−j+n−i−1n−i−1)\sum_{j=0}^{a_i} a_i \binom{j+i-1}{i-1}\binom{S-j+n-i-1}{n-i-1}-\sum_{j=0}^{a_i} j\binom{j+i-1}{i-1}\binom{S-j+n-i-1}{n-i-1}

前面那个 aia_i 可以直接搞出来，后面那个利用 (nm)=(nm−1)(n−m+1)\binom{n}{m}=\binom{n}{m-1}(n-m+1) 将 jj 改为 ii 再扔出来。

现在仅剩的问题就是快速计算：

f(n,m,i,k)=∑j=0k(j+i−1i−1)(m−j−1+n−in−i−1)f(n,m,i,k)=\sum_{j=0}^k \binom{j+i-1}{i-1}\binom{m-j-1+n-i}{n-i-1}

快速计算 f(n,m,i,k)f(n,m,i,k)？然而这个式子是拆不动了，考虑使用增量法计算。kk 的增量是好处理的，但是 ii 呢？不知道。从组合意义的角度考虑，ff 是将前 ii 个和 ≤k\le k 的数，且所有 nn 个数和为 mm 的方案数。相当于是将 mm 个相同的球放到 nn 个不同的盒子中，前 ii 个盒子最多只能放 kk 个球，相当于第 k+1k+1 个小球不在前 ii 个盒子里！那么枚举放的位置，插板有：

f(n,m,i,k)=∑j=i+1n(k+j−1j−1)(m−k−1+n−jn−j)f(n,m,i,k)=\sum_{j=i+1}^n \binom{k+j-1}{j-1}\binom{m-k-1+n-j}{n-j}

那么就可以使用这个式子维护 ii 的增量了。

查看代码 
#include <bits/stdc++.h>
using namespace std;
const int P = 998244353; 
const int N = 4000000; 

inline int read(void) {
    int x = 0, c = getchar_unlocked(); 
    while (!isdigit(c)) c = getchar_unlocked(); 
    while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar_unlocked(); 
    return x;
}
inline int poww(int a, int b) {
    int res = 1; 
    for (; b; b >>= 1, a = 1ll * a * a % P) if (b & 1) res = 1ll * res * a % P; 
    return res; 
}

int n; 
int a[500005], w[500005];
int fac[4000005], ifac[4000005]; 

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

struct Creeper {
	int n, m, i, k, ans; 
	Creeper(int n, int m, int i, int k) : n(n), m(m), i(i), k(k), ans(0) {
		for (int j = 0; j <= k; ++j)
			ans = (ans + 1ll * C(j + i - 1, i - 1) * C(m - j + n - i - 1, n - i - 1)) % P; 
	}
	void mvi(int mi) {
		for (int j = i + 1; j <= mi; ++j)
			ans = (ans - 1ll * C(k + j - 1, j - 1) * C(m - k - 1 + n - j, n - j)) % P; 
		i = mi;
	}
	void mvk(int mk) {
		for (int j = k + 1; j <= mk; ++j) 
			ans = (ans + 1ll * C(j + i - 1, i - 1) * C(m - j - 1 + n - i, n - i - 1)) % P; 
		k = mk; 
	}
};

int main(void) {
    for (int i = fac[0] = 1; i <= N; ++i) fac[i] = 1ll * fac[i - 1] * i % P; 
    ifac[N] = poww(fac[N], P - 2); 
    for (int i = N - 1; i >= 0; --i) ifac[i] = 1ll * ifac[i + 1] * (i + 1) % P; 
    for (int T = read(); T--; ) {
        n = read(); int ans = 0; 
        for (int i = 1; i <= n; ++i) a[i] = a[i - 1] + read(); 
        for (int i = 1; i < n; ++i) w[i] = read(); 
        
        Creeper A(n + 1, a[n] - 1, 1, a[n] - 1); 
        Creeper B(n, a[n], 1, a[n]); 
        Creeper C(n, a[n], 1, 0); 
        Creeper D(n + 1, a[n] - 1, 1, -1); 
        for (int i = 1; i < n; ++i) {
			int res = 0; 
			C.mvk(a[i]); D.mvk(a[i] - 1); 
			A.mvi(i + 1); B.mvi(i); C.mvi(i); D.mvi(i + 1); 
			res = (res + 1ll * i * A.ans) % P; 
			res = (res - 1ll * a[i] * B.ans) % P; 
			res = (res + 2ll * a[i] * C.ans) % P; 
			res = (res - 2ll * i * D.ans) % P; 
			ans = (ans + 1ll * res * w[i]) % P; 
		}
        printf("%d\n", (ans % P + P) % P); 
    }
    return 0;
}
组合计数进阶
https://james1badcreeper.github.io/cb620531/
本文作者
james1BadCreeper
发布于
2022年12月23日
许可协议
CC BY-NC-SA 4.0
署名-非商业性使用-相同方式共享 4.0 国际。

发布于 2022年12月23日
算法竞赛学习笔记数学

组合数学

数学

评论

若无法加载，请尝试刷新，欢迎讨论、交流和提出意见，支持 Markdown 与 LaTeX 语法（公式与文字间必须有空格）！