基础组合计数学习笔记

djwj233 · 2022-03-22 21:16:19 · 个人记录

啥都不会，只能任真学学。

这篇博客写得很语无伦次，建议跳着读。

排列组合常见模型

一些 naive 的东西

圆排列：Q_n^r=\dfrac{A_n^r}{r}；
错排：d(n)=(n-1)(d(n-1)+d(n-2))；
多重集排列：\dfrac{n!}{\prod n_i!}；
多重集组合：若 n_i 足够大，每个都比 r 大，那么就是 \binom{r+k-1}{k-1}（插板法）；

否则需要 \mathcal O(2^k) 容斥，具体做法就是枚举哪些超了 n_i，算出方案数。

简单格路计数

就是由 +1,-1 构成的数列，要求前缀和满足某个性质。

这种问题一般可以转化为在网格图上走，每次向上或向右。

前缀和体现在坐标系中就是一条斜线，把路径沿着斜线翻转还有双射啥的。

例题见 CF1204E。

更高明的格路计数可以看这篇。

Lucas 定理

碰到求一个组合数模一个小质数的问题，一定要记住：

组合数有 Lucas 定理！！！

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

这个东西一般是用来在 n,m 很大时计算组合数的，延伸性不强。

它的一个比较有意思的应用是判断 \binom{n}{m} 的奇偶性。结论是：

2\nmid \binom{n}{m}\Leftrightarrow n\ \&\ m =m

其中 \& 是按位与。

exLucas

就是不保证 p 是质数，然后可以质因数分解 + CRT 合并。

中间的处理就是扣出所有质因子然后前缀积。

Kummer 定理

质数 p 在 \binom{n}{m} 中的幂次等于 p 进制下 n 减去 m 需要借位的次数。

一些组合恒等式

下面均认为，对 \binom{n}{m} 式中 n/m 取负数或者 n<m 时值都是 0。

范德蒙德卷积

\sum_{i=0}^n\binom{n}{i}\binom{m}{i}=\sum_{i=0}^n\binom{n}{i}\binom{m}{m-i}=\binom{n+m}{m}

这样就可得一个化诈骗式子的东西：

\sum_{i=0}^n\binom{n}{i}^2=\binom{2n}{n}

组合乘幂次

考虑一个式子：

\sum_{i=0}^ni\binom{n}{i}=n2^{n-1}

就是先选一个，再钦定别的有没有。

类似地：

\sum_{i=0}^ni^2\binom{n}{i}=n(n+1)2^{n-2}

这个左边可以理解成选完 i 个再选两次，右边可以看成 A_n^22^{n-2}+n2^{n-1}。

如果要算 \sum_{i=0}^n i^k\binom{n}{i} 怎么办呢？可以用（后面的）斯特林数带进去推。结论是：

\sum_{i=0}^n i^k\binom{n}{i}=\sum_{t=1}^k {k\brace t}n^{\underline{t}}2^{n-t}

几个巧妙的恒等式

\sum_{i=0}^n\binom{i}{k}=\binom{n+1}{k+1}

把最右边选的和后面的去掉即可。

\binom{n}{m}\binom{m}{k}=\binom{n}{k}\binom{n-k}{m-k}

这个东西还可以套娃起来，具体再推一遍。

\sum_{i=0}^n\binom{n-i}{i}=Fib_{n+1}

回想斐波那契的贡献形式，选了额外的那条路就是跳了一级。

这个式子非常有意思（

二项式反演

区别于 DP 的套路化、模板化，组合计数的精髓是容斥、反演。

二项式反演的本质就是容斥，就是 \sum_{i=0}^n(-1)^i\binom{n}{i}=[n=0]。

回忆容斥原理的形式，每个大小为 i 的集合的贡献是 (-1)^i。

考虑一种特殊的容斥，即每个交集的大小仅与所交的集合数量有关。这样公式变成：

ans=\sum_{i=1}^n(-1)^i \binom{n}{i}f(i)

我们发现里面的系数就是二次项系数。这有什么用呢？

定理：f(x)=\sum_{i=1}^n (-1)^i\binom{n}{i}g(i)\Leftrightarrow g(x)=\sum_{i=1}^n (-1)^i\binom{n}{i}f(i)。

换言之，(-1)^i\binom{n}{i} 作为一个变换的系数时，其逆变换系数就是本身。

事实上，我们如果把上面这个东西加以简单的代数变换，可以得到：

f(x)=\sum_{i=1}^n \binom{n}{i}g(i)\Leftrightarrow g(x)=\sum_{i=1}^n (-1)^{n-i}\binom{n}{i}f(i)

这个东西非常有用，实际意义就是恰好转钦定，基本做法就是：

要求的是一个都没有或恰好有 k 个。

做法是钦定有 i 个有，别的不知道。

然后算，算出来按 i 奇减偶加。

斯特林数

第二类斯特林数

第二类斯特林数的定义是把 n 个不同的球装进 m 个相同的盒子里，要求它们均非空，记为 S(n,m)={n\brace m}。

容易发现 n<m 时必然有 {n\brace m}=0。

{n\brace m}={n-1\brace m-1}+m{n-1\brace m}

边界是 {n\brace 0}=[n=0]。

其意义是：将第 n 个数单独作为一个集合 + 构造出 n-1\brace m-1 的方案后再塞进其中的一个集合。

可以考虑一个二项式反演的思路。

{n\brace m}=\dfrac{\sum_{i=0}^m(-1)^{m-i}\binom{m}{i}i^n}{m!}=\sum_{i=0}^m\dfrac{(-1)^{m-i}i^n}{i!(m-i)!}

前面那个式子中，注意千万不能在式子里除掉 i!，因为这个反演基于的假设是 m 个盒子不同，在最后才把 m! 除去。

另外，后面一个式子中每一项不一定是整数，但是由组合意义，加起来一定是整数。

为了便于处理，保留整数时一般还是用前面的式子。

naive 的性质 A：

n^k=\sum_{i=0}^k\binom{n}{i}{k\brace i}i!

两边都表示 k 球不同、n 盒不同且盒可空的方案数。

第一类斯特林数

表示将 n 个不同的球装进 k 个互不区分的非空轮换中的方案数，记为 s(n,m)={n\brack m}。

与第二类斯特林数不同的是，这里每个盒子变成了轮换。

轮换就是 [A,B,C]=[B,C,A]=[C,A,B]\ne [C,B,A] 这样的东西。

{n\brack m}={n-1\brack m-1}+(n-1){n-1\brack m}

不难发现就是把第二类斯特林数的那个系数从 m 变成了 n-1。

这个递推式是显然的，我们只需要把每个轮换中最小的那个数看作是它的起始位置即可。

第一类斯特林数暂未发现有实用的通项式。
naive 性质：

\sum_{i=0}^n {n\brack i}=n!

将 n 阶排列按单调性分成若干轮换；将 i 个轮换根据最小项降序排序再拼成一个排列。二者双射。

（也可以通过置换环构造双射）

上升幂、下降幂与普通幂

由上面的性质 A，约去 i! 可以得到：

n^k=\sum_{i=0}^k {k\brace i}\times n^{\underline{i}}

事实上这个东西也可以通过归纳得到。

上升幂怎么搞呢？实际上有：

n^{\overline{k}}=\sum_{i=0}^k {\ k\ \brack \ i\ }\times n^i

这个东西也可以归纳证明。

需要注意的是，这两个和式目标方向都是向更高一档的。

那么，怎么反着做回来捏？我们注意到 n^{\overline{k}}=(-n)^{\underline{k}}(-1)^k，这样：

(-n)^{\underline{k}}=(-1)^k\sum_{i=0}^k{\ k \ \brack \ i\ }n^i

把其中的 n 换成 -n：

n^{\underline{k}}=\sum_{i=0}^k{\ k \ \brack \ i\ }(-1)^k(-n)^i=\sum_{i=0}^k{\ k \ \brack \ i\ }(-1)^{k-i}n^i

很漂亮的一个形式！对称地我们有：

n^k=\sum_{i=0}^k{k\brace i}(-1)^{k-i}n^{\overline{i}}

回顾一下，我们对第二类斯特林数进行二项式反演得到 普通幂转下降幂：n^m=\sum_{i=0}^m{m\brace i}n^{\underline{i}}；

然后通过组合意义证明 上升幂转普通幂 n^{\overline{m}}=\sum_{i=0}^m{m\brack i}n^i；

说明：右边可以看作对一个 m 阶排列的每个置换环染色成 n 种颜色之一。

左边考虑怎么计算这个东西。不难发现，当第 k 个数被加进来时有两种选择：

接到之前的某个数之后：k-1 种方案；

自己成为一个新的置换环并染一个色：n 种方案。

所以总方案数就是 \prod_{k=1}^m(n+k-1)=n^{\overline{m}}。

最后通过往里面代负数进去得到了它们的反演形式。

我们考虑用下降幂去表示一个多项式：

f(x)=\sum_{i=0}^n b_ix^{\underline{i}}

它有什么性质？

我们考虑对其单点求值：

f(x)=\sum_{i=0}^n b_i\dfrac{x!}{(x-i)!}

可以 \mathcal O(n) 求出，但是再仔细看看：

\dfrac{f(x)}{x!}=\sum_{i=0}^n b_i\times\dfrac{1}{(x-i)!}

我们发现这是一个卷积形式的式子。换言之，点值表示 和 下降幂多项式表示 可以 \mathcal O(n\log n) 转化。

但是显然要一些多项式的东西，所以咕咕咕了。

斯特林数的恒等式太多辣！！就咕掉辣！！！

来几道例题，没有多项式：

P4609 [FJOI2016]建筑师

你花了好长时间去推一个 DP 式，结果发现式子就是第一类斯特林数......

这样答案就是

\sum_{i=0}^{n-1}\binom{n-1}{i}{\ i\ \brack A-1}{\ n-1-i\ \brack B-1}

直接暴力只有 40 分，怎么办呢？貌似只能预处理什么东西。

但是不是，这个东西可以直接写成：

{\ n-1\ \brack A+B-2}\binom{A+B-2}{A-1}

根据组合意义它是对的。

启示：卷积形式的斯特林数可以尝试合并。

P6667 [清华集训2016] 如何优雅地求和

我们注意到多项式是点值表示的，考虑转成下降幂形式：

\begin{aligned} \sum_{k=0}^n f(k)\binom{n}{k}x^k(1-x)^{n-k} &=\sum_{k=0}^n \left(\sum_{i=0}^m b_ik^{\underline{i}}\right)\binom{n}{k}x^k(1-x)^{n-k}\\ &=\sum_{i=0}^m b_i\sum_{k=0}^n k^{\underline{i}}\binom{n}{k}x^k(1-x)^{n-k}\\ &=\sum_{i=0}^m b_i\sum_{k=0}^n \dfrac{n!}{(k-i)!(n-k)!}x^k(1-x)^{n-k}\\ &=\sum_{i=0}^m b_in^{\underline{i}}\sum_{k=i}^n \binom{n-i}{k-i}x^k(1-x)^{n-k}\\ &=\sum_{i=0}^m b_in^{\underline{i}}x^i\sum_{k=i}^n \binom{n-i}{k-i}x^{k-i}(1-x)^{n-k}\\ &=\sum_{i=0}^m b_in^{\underline{i}}x^i \end{aligned}

直接算是 \mathcal O(m) 的吗？其实转成下降幂多项式的过程就需要 \mathcal O(m\log m) 的 NTT。

考虑避开 NTT，我们回顾 a 的定义式 a_x=\sum_{i=0}^m b_ix^{\underline i}，有没有一种方法可以直接从 a_x 导出答案呢？

是可以的但是我看不懂，打个 \mathcal O(m^2) 的算了。看来 m\le 2\times 10^4 稳过

启示：碰到 \sum_{i=0}^n i^k\binom{n}{i} 类似的结构，可以考虑斯特林数转成下降幂。

P4827 [国家集训队] Crash 的文明世界

这个东西在 k=1 时显然可以换根 DP，往上怎么做？

一个比较自然的思路是，我们可以维护每个 \sum \text{dist}^i 的值然后转移，但这是 \mathcal O(nk^2) 的，寄了。

我们考虑一个转移的过程，需要把 d 变成 d+1，这时可以用下降幂进行转移！！！

具体地，我们发现：

d^{\underline{i}}=d(d-1)(d-2)\cdots(d-i+2)(d-i+1)

(d+1)^{\underline{i}}=(d+1)d(d-1)(d-2)\cdots(d-i+2)

也就是说 (d+1)^{\underline{i}}-d^{\underline{i}}=id^{\underline{i-1}}，可以直接计算！

（如果你眼神够好，可以发现这个东西非常像 (x^n)^{\prime}=nx^{n-1}）

这样我们套路地拆开普通幂变成下降幂再维护即可。

本质上这种方法利用了下降幂连续性强，易于（全局）转移的性质。

启示：如果一个转移涉及到维护 \sum a^m 的值，且有全局操作 a^m\to (a+x)^m。

那么就既可以 \mathcal O(m^2) 二项式维护，也可以考虑化成上升 / 下降幂 \mathcal O(m) 做。

U117218 经典问题 1

首先会了一个 \mathcal O(n^6) 的屁用没有的 DP，然后我就不会了。

看了题解，这个斯特林反演真的牛逼！！！

我们考虑把卷积扔掉，把点数扔掉，全部扔掉。

记 f_{i,j} 为用了 i 条边形成 j 个联通块，g_{i,j} 为用了 i 条边形成 j 个块（块内不一定联通，但块间无边）。有：

g_{i,j}=\sum_{k=j}^n {k\brace j}f_{i,k}

这样：

f_{i,j}=\sum_{k=j}^n (-1)^{k-j}{\ k\ \brack\ j\ }g_{i,k}

我们只需考虑如何计算 g_{m,j} 就可以辣！但是又不会了

再加一维！记 dp_{i,j,k} 为 i 条边、j 个点、k 个块的方案数，有：

dp_{i,j,k}=\sum_{a\le i}\sum_{b\le j}\sum_{c\le k}dp_{a,b,c}\times dp_{i-a,j-b,k-c}

三维卷积，不过好像可以快速幂优化暴力卷积成 \mathcal O(n^4\log n)，貌似还是过不去而且没啥优化空间。

可以把 i 这维的转移压下去吗？我们考虑将 i 的含义转成最多能连 i 条边的方案数。

这样只需在算贡献时乘上一个 \binom{i}{m} 即可。复杂度还是不太行......

但是不要急！我们的目标只有 f_{m,1}！再看：（下面的 dp 是原始定义）

f_{m,1}=\sum_{k=1}^n (-1)^{k-1}(k-1)!\times dp_{m,n,k}

我们在 DP 状态里去掉 k 这一维，直接把 (-1)^{k-1}(k-1)! 算到式子里！！！

这回再写一遍式子：（这里的 dp 是后来的定义）

ans=\sum_{t=m}^{\binom{n}{2}}dp_{t,n}\binom{t}{m}

由于需要 (k-1)! 而不是 k!，我们钦定 1 号点在第一个连通块再额外考虑答案。太神仙了！！！

十二重计数法

有 n 球 m 盒。

显然是 $m^n$。 $\mathrm{II}$：球不同，盒不同，容量一。显然是 $A_{m}^n$。 $\mathrm{III}$：球不同，盒不同，不能空。不那么显然了。可以容斥吗？式子列出来是 $$ \sum_{i=0}^m (-1)^{m-i}\binom{m}{i}i^n $$ 其实就是 $m!{n\brace m}$ 辣。 $\mathrm{IV}$：球不同，盒相同，无限制。就是 $\sum_{i=0}^n{n\brace i}$，这东西没有什么好的恒等式，但是多项式是可以求一整行的。另外 $n=m$ 时这东西叫贝尔数 $B_n$。有递推式： $$ B_n=\sum_{i=0}^{n-1} \binom{n-1}{i}B_{i} $$ 注意这里是 $\binom{n-1}{i}$，也就是我们取出第一个再考虑别的，否则会数重。 $\mathrm{V}$：球不同，盒相同，容量一。显然是 $[m\ge n]$。![](https://啧.tk/hanx) $\mathrm{VI}$：球不同，盒相同，不能空。就是 $n\brace m$ 的定义。 $\mathrm{VII}$：球相同，盒不同，无限制。插板！构造双射后可知是 $\binom{n+m-1}{m-1}$。 $\mathrm{VIII}$：球相同，盒不同，容量一。相当于在 $m$ 个盒子中选出 $n$ 个装球，答案为 $\binom{m}{n}$。 $\mathrm{IX}$：球相同，盒不同，不能空。最纯正的插板法，答案是 $\binom{n-1}{m-1}$。 $\mathrm{X}$：球相同，盒相同，无限制。开始牛逼起来了！这个东西是拆分数，可以 $\mathcal O(n^2)$ DP，但是会 T。正解是用多项式去卷。答案是 $p(n+m,m)$。 $\mathrm{XI}$：球相同，盒相同，容量一。答案是 $[n\le m]$。 $\mathrm{XII}$：球相同，盒相同，不能空。是 $p(n,m)$。 ## 单位根反演学一个不太用得到的东西。公式是： $$ [n\mid x]=\dfrac{1}{n}\sum_{i=0}^{n-1}\omega_n^{ix} $$ 其实挺自然的，就是说，如果 $n\nmid x$ 那么得到的 $n$ 个向量就是均匀的，所以是 $0$。在模意义下，$\omega_n$ 可以看成 $g^{\frac{P-1}{n}}$，其中 $g$ 是原根，$P$ 是质数。更常用的一个形式是： $$ [x\equiv y\pmod {n}]=\dfrac{1}{n}\sum_{i=0}^{n-1}\omega_n^{i(y - x)} $$ #### 例题 - [LOJ #6485. LJJ 学二项式定理](https://loj.ac/p/6485) 题目要求： $$ \sum_{i=0}^n\binom{n}{i}s^i a_{i\ \bmod\ 4} \mod 9982444353 $$ 组合乘值数，自然想到二项式定理。但是这个 $a_{i\ \bmod\ 4}$ 怎么处理？解法是单位根反演。我们把 $\bmod$ 拆开： $$ \begin{aligned} \sum_{i=0}^n\binom{n}{i}s^i a_{i\ \bmod\ 4}&= \sum_{i=0}^n\binom{n}{i}s^i \sum_{j=0}^3 a_{j}[i\equiv j\pmod{4}] \\ &= \sum_{j=0}^3a_j\sum_{i=0}^n\binom{n}{i}s^i\times \dfrac{1}{4}\sum_{k=0}^{3}\omega_4^{k(i-j)} \\ &= \dfrac{1}{4}\sum_{j=0}^3a_j\sum_{k=0}^{3}\omega_4^{-kj}\sum_{i=0}^n\binom{n}{i}s^i\times \omega_4^{ki} \\ &= \dfrac{1}{4}\sum_{j=0}^3a_j\sum_{k=0}^{3}\omega_4^{-kj}\sum_{i=0}^n\binom{n}{i}(s\omega_4^{k})^i\times 1^{n-i} \\ &= \dfrac{1}{4}\sum_{j=0}^3a_j\sum_{k=0}^{3}\omega_4^{-kj}(1+s\omega_4^{k})^n \end{aligned} $$ 这样就可以了！注意那个 $\dfrac{1}{4}$ 不要手贱推成 $\dfrac{1}{3}$...... - [P5591 小猪佩奇学数学](https://www.luogu.com.cn/problem/P5591) 可以把那个 $\left\lfloor\dfrac{i}{k}\right\rfloor$ 拆成 $\dfrac{i-i\bmod k}{k}$，推推推。 $$ \begin{aligned} \sum_{i=0}^n\binom{n}{i}p^i\left\lfloor\dfrac{i}{k}\right\rfloor&= \sum_{i=0}^n\binom{n}{i}p^i\times\dfrac{i-i\bmod k}{k} \\ &= \dfrac{1}{k}\left(\sum_{i=0}^n\binom{n}{i}p^ii-\sum_{i=0}^n\binom{n}{i}p^i(i\bmod k)\right) \end{aligned} $$ 我们令减号前面是 $A$，后面是 $B$。那么： $$ \begin{aligned} A &= \sum_{i=0}^n\binom{n}{i}p^ii\\ &= \sum_{i=0}^n\dfrac{n^{\underline{i}}}{i^{\underline{i}}}p^i\times i \\ &= n\sum_{i=0}^n\dfrac{n^{\underline{i-1}}}{i^{\underline{i-1}}}p^i\\ &= np\sum_{i=0}^{n-1}\binom{n-1}{i}p^i \\ &= np(1+p)^{n-1} \end{aligned} $$ 算 $B$ 是重难点。 $$ \begin{aligned} B &= \sum_{i=0}^n\binom{n}{i}p^i (i\bmod k)\\ &= \sum_{i=0}^n \binom{n}{i}p^i\sum_{j=0}^{k-1}j[k\mid i - j] \\ &= \sum_{i=0}^n \binom{n}{i}p^i\sum_{j=0}^{k-1}j\times \dfrac{1}{k}\sum_{t=0}^{k-1}\omega_{k}^{tj-ti} \\ &= \dfrac{1}{k}\sum_{j=0}^{k-1}j\sum_{t=0}^{k-1}\omega_{k}^{tj}\sum_{i=0}^n \binom{n}{i}(p\omega^{-t})^i1^{n-i} \\ &= \dfrac{1}{k}\sum_{j=0}^{k-1}j\sum_{t=0}^{k-1}\omega_{k}^{tj} (p\omega^{-t} + 1)^n \end{aligned} $$ 直接暴力是 $\mathcal O(k^2\log k)$ 的，可以拿到 60 分。但是可以继续推： $$ \begin{aligned} B &= \dfrac{1}{k}\sum_{j=0}^{k-1}j\sum_{t=0}^{k-1}\omega_{k}^{tj} (p\omega^{-t} + 1)^n \\ &= \dfrac{1}{k}\sum_{t=0}^{k-1}(p\omega^{-t} + 1)^n\times \sum_{j=0}^{k-1}j\omega_{k}^{tj} \\ \end{aligned} $$ 记 $a=\omega_{k}^t$，后面那个式子就变成 $\sum\limits_{j=0}^{k-1}ja^j$，是一个经典的幂次乘指数的形式。推一推： $$ \begin{aligned} \sum\limits_{i=0}^{k-1}ia^i &= \sum_{i=1}^{k-1}\sum_{j=i}^{k-1} a^j =\sum_{i=1}^{k-1}\dfrac{a^k-a^i}{a-1} \\ &=\dfrac{1}{a-1}\left((k - 1)a^k - \sum_{i=1}^{k-1}a^i\right) \\ &=\dfrac{1}{a-1}\left((k -1)a^k - \dfrac{a^k-a}{a-1}\right) \end{aligned} $$ 这样复杂度就是 $\mathcal O(k\log k)$ 的了。为什么 $k$ 要是 $2^w$ 形式的呢？因为 $998244353=119\times 2^{23}+1$，这样就能有单位根了。 **不要忘记特判 $a=1$！！！** **总结：碰到组合式子里有对 $i$ 模 / 整除的可以考虑单位根反演。**

基础组合计数 学习笔记