简介
组合知识计数
CF 869C The Intriguing Obsession
$n$ 个点存在完美匹配的带标号无根树
$\frac{n!}{(2!)^{\frac n2}\cdot (\frac n2)!}\cdot (\frac n2)^{\frac n2 - 2}\cdot 4^{\frac n2-1}$
$n$ 点 $n-1$ 条边的链选择 $m$ 个互不相邻的边的方案数为 $\binom{n-m}{m}$
简要题意：现在有 $n$ 个骨牌，每个骨牌有左右两边，每边只能是黑色和白色且不能交换，现在给定 $n$ 个骨牌，有些骨牌的的某一些边已经固定了颜色，剩下的位置需要你来染色，现在一种合法的染色方案为将 $n$ 个骨牌染好色之后，存在一个圆排列满足，任亮两个相邻骨牌的相邻的两个边的颜色不同，即第 $i$ 个骨牌的右边和第 $i+1$ 个骨牌的左边的颜色不同，求有多少种染色方案
$n\le 10^5$
简要题解：容易发现对于任意一种合法的染色方案，不考虑左右边，黑色和白色的个数都必须是 $n$，令 $cntb$ 和 $cntw$ 分别表示已经固定的白色和黑色的个数，那么现在我们就有一个方案数 $\binom{2n-cntb-cntw}{n-cntw}$
这里面一定包含了所有合法方案，但有一些方案不合法的，我们考虑什么情况下会出现不合法方案，另外我们注意到我们这样染色 $00$ 和 $11$ 的块一定是一样多的，因为 $cntb=cntw=n$ 且 $01$ 和 $10$ 不影响 $cntb$ 和 $cntw$ 的差值
通过观察我们能够发现，只要 $00$ 和 $11$ 的数量大于等于 $1$，方案就一定是合法的，那么我们只要把 $00$ 和 $11$ 出现 $0$ 次的不合法方案减掉即可，时间复杂度 $O(n)$
简要题意：给定一个 $n$ 个点 $m$ 条边的简单无向图，如果原图有 $k$ 个连通块，求添加 $k-1$ 条边是整个图连通的方案数
$n,m\le 10^5$
简要题解：我们令 $d_i$ 表示第 $i$ 个连通块的度数，$s_i$ 表示第 $i$ 个连通块的大小，那么我们有
这个式子大概就是我们枚举每个连通块的度数，然后根据 $prufer$ 序列来计数，后面那个 $\prod$ 是因为每个连通块向外连边有 $s_i$ 种选择
这个式子我们利用多项式定理来可以得到 $ans=n^{k-2}\prod_{i=1}^ks_i$
简要题意：给定 $n,m$，现在要求所有长度为 $n$ 的序列，序列中每个位置只能填 $[1,m]$，的本质不同的子序列的个数的和
$n,m\le 10^6$
简要题解：我们考虑对于每种子序列在其出现的序列中的第一次出现位置来计数，不妨令第一次出现的结束位置为 $i$，子序列的长度为 $j$，那么我们首先有 $\binom{i-1}{j-1}m^{j+n-i}$，显然 $[i+1,n]$ 都是随便选，然后这个这样的子序列有 $m^j$ 种，出现位置的选择有 $\binom{i-1}{j-1}$，现在的问题是 $[1,i]$ 中剩下的 $i-j$ 个位置要如何填，简单思考可以发现每个位置只有一个数不能填，即它后面的第一个属于我们枚举的子序列的位置的那个数，所以答案为 $\sum_{i=1}^n\sum_{j=1}^i\binom{i-1}{j-1}m^{j+n-i}(m-1)^{i-j}$，注意这个式子没有加上空子序列的答案，所以我们计算完后需要再加上 $m^n$，能够发现这个式子很像二项式定理，我们考虑向这个方向化简这个式子
时间复杂度 $O(n\log n)$
简要题解：给定一个长度为 $n$ 的数字和整数 $k$，求将这个数字划分成不超过 $k$ 段的所有划分方法的价值和，定义一种划分方法的价值为它各段的价值和，一段数字的价值就是这个数字的值，例如：$114514$ 的一种划分 $(114)(5)(14)$ 的总价值是 $114+5+14=133$
$1\le k\le n\le 10^6$
简要题解：我们考虑对于每个区间 $[l,r]$ 计算它的价值会被计算所少次
为了方便设 $l>1\wedge r <n$，$s=l-1,t=n-r$
容易得到次数就是 $\sum_{d=2}^{k-1}\sum_{i=1}^{d-1}\binom{s-1}{i-1}\binom{t-1}{d-i-1}=\sum_{d=2}^{k-1}\binom{s+t-2}{d-2}=\sum_{d=0}^{k-3}\binom{s+t-2}{d}$，这是一个组合数前缀和的形式
容易发现，这个东西只跟 $[l,r]$ 的长度有关，我们令 $f_i$ 表示长度为 $i$ 的区间的和，那么可以得到随着 $i$ 的增加，这个组合数的上指标在减少，且总共只会移动 $O(n)$，我们可以 $O(n)$ 维护它的变化
另外前缀和后缀以及 $k\le 2$ 的情况要单独考虑，时间复杂度 $O(n)$
简要题意：给定一个长度为 $n$ 的序列 $a_i$，求 $\sum_{i=1}^n\sum_{j=i}^nf_{i,j}$，其中 $f_{i,j}=\binom{\sum_{k=i}^ja_i}{a_i,a_{i+1},\cdots,a_j}\bmod p$
$n\le 5\times 10^5,a_i\le 10^{18},p\in \lbrace 2,3,5,7\rbrace$
简要题解：容易得到 $f_{l,r}=f_{l,r-1}\times \binom{a_r+\sum_{i=l}^{r-1}a_i}{a_r}$，我们考虑枚举左端点，维护右端点递增的答案，每次相当于乘上一个组合数，这个组合数我们可以用 $lucas$ 定理计算，这样做的时间复杂度是 $O(n^2\log a_i)$
从另一个角度思考我们发现每次右端点递增的时候都是乘上一个组合数，那么有没有可能到某一个时候乘出来 $0$，这样就显然没必要继续乘了
我们深入考虑一下什么情况下会变成 $0$，考察 $kummer$ 定理，我们知道 $\binom{n+m}{m}$ 所含有 $p$ 的幂次等价于 $n$ 和 $m$ 在 $p$ 进制加法下的进位次数，那么我们知道这个组合数变为 $0$ 的条件是前缀和发生进位，那么我们如果变成 $0$ 就 $break$ 的时间复杂度就变成了 $O(np\log^2 a_i)$，因为对于一个左端点，最多只会乘 $p\log a_i$ 次
但是这样仍然不能通过此题，容易发现每次都做一遍 $lucas$ 太慢了，我们发现只需要每次把不是 $0$ 的位拿出来单独计算即可，这样时间复杂度就变成了 $O(np\log a_i)$，可以通过此题，另外对于 $a_i=0$ 的位置，我们只需要记录一个 $nxt_i$ 表示下一个不为 $0$ 的位置即可
简要题意：给定 $n,m$，求所有长度为 $n$ 的每个位置为 $[1,m]$ 的序列的价值和，定义一个序列的价值为其本质不同的子序列的数量
$n,m\le 10^6$
简要题解：我们首先考虑一个比较暴力的做法，我们枚举子序列的长度的长度 $i$，同时对于每个子序列，我们在其第一次出现的结束位置计数，我们令这个位置为 $j$，那么我们可以得到如下式子 $ans=\sum_{i=1}^nm^i\sum_{j=i}^n\binom{j-1}{i-1}(m-1)^{j-i}m^{n-j}$，组合数枚举的是子序列出现的位置，$(m-1)^{j-i}$ 表示除了这个子序列之外其他数的选择方案，注意到每个位置的不能与其后第一个属于该子序列的数相同，其他 $m-1$ 种数都可以选，$m^{n-j}$ 表示后面可以随便填，我们考虑化简
这个式子我们直接暴力即可
简要题意：现在有 $T$ 组询问，每次询问给定 $n$，求所有长度为 $n$ 的每个位置是 $[1,n]$ 的序列的价值和，定义一个序列的价值和为 $\sum_{i=k}^{\min(k,n-1)+n-1}\frac{lcm(i-k+1,n)}{k+1}$，其中 $k$ 是该序列中未出现的数的种数
$n,T\le 10^6$
简要题解：简单转化后容易得到 $ans=(\sum_{i=1}^n[i,n])\times \sum_{i=1}^n\frac{1}{n-i+1}\binom{n}{i}n
^i$，前面两个东西无关，我们先考虑化简前面那个东西，考虑莫比乌斯反演的部分，容易得到前面那个东西为 $\sum_{i=1}^n[i,n]=n\sum_{d|n}\frac{n}{d}\frac{[n=d]+\varphi(\frac{n}{d})}{2}$，这个可以 $O(n\log n)$ 预处理，我们考虑化简后半部分
动态规划计数
利用 $dp$ 计数的关键是能够正确定义状态，使得能够进行正常的转移并且不会产生重复计数
Luogu P6146 [USACO20FEB]Help Yourself G
简要题意：给定一个长度为 $n$ 的排列 $p_i$，现在你可以若干次操作，每次操作选定一个区间 $[l,r]$，将区间 $[l,r]$ 内的数都变成 $[l,r]$ 的最小值，求可能会有多少种序列
$n\le 3000$
简要题解：我们令 $l_i$ 表示 $p_i$ 左边第一个比 $p_i$ 小的位置，$r_i$ 表示 $p_i$ 右边第一个比 $p_i$ 小的位置，容易在最终序列中得到 $p_i$ 能够控制的区间一定是 $[l_i+1,r_i-1]$ 的一个子区间
那么我们考虑 $dp$，令 $f_{i,j}$ 表示前 $i$ 个 $p$，控制了 $[1,j]$ 这个区间，容易得到转移如下：
1
2
3
4
5for (int i = 1; i <= n; ++i) {
for (int j = 0; j <= n; ++j) f[i][j] = f[i - 1][j];
for (int j = l[i] + 1; j <= r[i] - 1; ++j)
for (int k = l[i]; k < j; ++k) f[i][j] = (f[i][j] + f[i - 1][k]) % p;
}注意到 $k$ 的枚举是一个区间，我们求一个前缀和即可，时间复杂度 $O(n^2)$
2020-2021 ICPC Southeastern European Regional Programming Contest (SEERC 2020) F Fence Job
简要题意：给定一个长度为 $n$ 的序列 $a_i$，每秒会随机选择一个大于 $0$ 的 $a_i$ 将其减 $1$，求 $m$ 秒后期望有多少个 $a_i=0$
$n\le 15,m,a_i\le 100$
简要题解：我们考虑枚举哪些 $a_i$ 最终会变成 $0$，我们令这些 $a_i$ 为集合 $S$，令 $cnt_S$ 表示 $|S|$ 的大小，$sum_S$ 表示 $S$ 中 $a_i$ 的和
我们考虑用 $DP$ 计算所有序列的概率和，令 $f_{i,S}$ 表示现在过了 $i$ 秒，$S$ 中的 $a_k$ 都已经变成 $0$ 的概率和，注意我们记录后面某个 $a_k$ 会变成 $0$ 的状态，所以我们的序列中有一个特殊元素 $x$ 表示这个位置填的东西待定，那么我们 $f_{i,S}$ 的向后转移有两种选择，第一种是选择一个新的 $a_k$，它变成了 $0$，也就意味着第 $i+1$ 填 $k$，前 $i$ 秒中有 $a_k-1$ 个 $x$ 会变成 $k$，那么贡献为 $\binom{i-sum_{S}}{a_k-1}\frac{1}{n-cnt_{S}}f_{i,S}$，如果填一个 $x$，那么贡献为 $\frac{1}{n-cnt_S}f_{i,S}$
但是这个东西并不是答案，我们还需要将剩下的 $x$ 变成 $U-S$ 中的数字，显然每种序列都是不同的，所以我们需要在乘上一个 $g_{m-cnt_S,U-S}$ 表示在 $U-S$ 中选择 $m-cnt_S$ 个数字组成的序列个数
时间复杂度 $O(2^nm^2)$
2020 China Collegiate Programming Contest, Weihai Site E So Many Possibilities…
容斥DP计数
这里的容斥不是利用反演来计数，一般情况下都是利用最简单的减法原理来计数，在这种 $dp$ 中，我们通常定义 $f$ 为没有重复计数的方案，而在转移过程中的需要容斥的东西，我们通过 $f$ 之间的关系来将其容斥，一般情况下，我们还需要保证在容斥的过程中，每一种不合法的情况只会被减掉一次
简要题意：给定一个 $n\times m$ 的棋盘和 $k$ 个黑色的格子，求从左上角到右下角且不经过任何黑色格子的方案数，只能向右或者向下走
$n,m\le 10^5,k\le 2000$
简要题解：我们考虑容斥 $dp$，令 $f_i$ 表示从左上角到第 $i$ 个黑色格子且中间不经过任何其它黑色格子的方案数
我们考虑如何从 $f_j$ 转移到 $f_i$，注意到任何一个不合法路径的存在第一个经过的黑色格子，我们可以按照第一个经过的黑色格子来区分所有不合法路径，那么我们枚举第一个黑色格子，容易得到 $f_i=\binom{x_i-1+y_i-1}{x_i-1}-\sum f_j\binom{x_i-x_j+y_i-y_j}{x_i-x_j}$时间复杂度 $O(n+k^2)$
简要题意：给定一个长度为 $n$ 的序列 $a_i$ 以及 $k$ 和 $L$，$a_i\in[1,k]$ 或者 $a_i=-1$，对于 $a_i=-1$ 的点，你需要填一个 $[1,k]$ 的数字，满足不存在长度大于等于 $L$ 的连续相等段
$n \le 10^5,k\le 100$
简要题解：我们考虑容斥 $dp$，令 $f[i][j]$ 表示前 $i$ 个数字已经填完，第 $i$ 个数字是 $j$，$g[i]=\sum_{j=1}^k f[i][j]$
转移的时候，我们枚举第 $i$ 位填数字 $j$，然后将不合法的情况减掉，容易得到不合法的情况就是 $g[i-L]-f[i-L][j]$，时间复杂度 $O(nk)$
单独计算每个物品的贡献
某些情况下，可能多个物品只会产生一个贡献，这个时候我们可以规定这一个贡献是由哪个物品产生的
简要题意：给定 $n$ 线段 $[l_i,r_i]$，保证不存在任何两条线段的左端点或右端点重合，定义若干条线段的复杂度为这些线段的并形成的连通块的个数，求这 $n$ 条线段的所有子集的复杂度之和
$n\le 10^5,1\le l_i\le r_i\le 2n$
简要题解：我们考虑对于每一个连通块，我们认为是左端点最靠左的那个线段才有贡献
那么我们考虑单独计算每个线段的贡献
注意到线段 $i$ 如果能作出贡献，那么一定不存在线段 $j$，$l_j< l_i < r_j$
不妨设这样的线段 $j$ 的个数为 $s$，那么线段 $i$ 的贡献就是 $2^{n-s-1}$，注意到此题左端点不会重合
统计线段 $j$ 的数量可以用差分实现，时间复杂度 $O(n)$
通过将计数转换成求期望
适用情况，求所有情况下，某个东西的总和
通过方案数求第 k 小
这种情况下，第 $k$ 小一般指的是排列或者是字符串
最普通的方法就是我们对于每一位从小到大枚举，然后通过已经计算出的方案数来选择