容斥与反演技巧（一）

云浅知处 · 2022-10-19 21:12:17 · 个人记录

搬运自云浅的小窝

二项式反演

我们直接上式子好了

一般有两种形式，第一种是

f(n)=\sum_{i=0}^n\binom{n}{i}g(i)\iff g(n)=\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}f(i)

第二种是

f(n)=\sum_{i=n}^m\binom{i}{n}g(i)\iff g(n)=\sum_{i=n}^m\binom{i}{n}(-1)^{i-n}f(i)

第二种比第一种更加常用。

一般来说我们的 f(n) 是钦定 n 个元素必须选中，剩下的随便选的方案数。注意 f 并非单纯的后缀和。

例题

球的染色

有 n 个球排成一列，每个球可以染成 m 种颜色，相邻球的颜色不能相同，但是每种颜色至少出现一次，问方案数。

如果没有至少出现一次的限制那么答案就是 m\times (m-1)^{n-1}。

考虑转化为恰好有 0 个颜色没有出现过，那么设 f(k) 为钦定某 k 种颜色没有出现的方案数，那么 f(k)=(m-k)\times (m-k-1)^{n-1}。

设 g(k) 为恰好 k 个颜色没有出现过的方案数，那么

f(k)=\sum_{i=k}^m\binom{i}{k}g(i)\iff g(k)=\sum_{i=k}^m(-1)^{i-k}\binom{i}{k}f(i)=\sum_{i=k}^m(-1)^{i-k}\binom{i}{k}(m-k)\times (m-k-1)^{n-1}

那么 g(0) 就是答案啦

SDOI2016 排列计数

考虑设 f(x) 为钦定 x 个位置必须放对，剩下的随便放，那么 f(x)=\binom{n}{x}(n-x)!=\frac{n!}{x!}。

乘上 \binom{n}{x} 的原因是我们要先选出来这 x 个位置。然后 g(x) 表示恰好放对 x 个位置的方案数，我们有

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

然后你用 f(x)=\frac{n!}{x!} 化简一下发现

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

前后都可以 O(n) 预处理，于是这题就做完了。AC Code

BZOJ2839 集合计数

先选出 x 个元素必须在交集里面，那么剩下的 n-x 个元素可以构成 2^{n-x} 个集合，可以随便选但不能一个都不选，因此方案数为

f(x)=\binom{n}{x}\left(2^{2^{n-x}}-1\right)

然后设 g(x) 为交集大小恰好为 k 的方案数，那么

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

注意到只有一次询问，因此可以先算出来 f 然后直接算出来 g。不难在 O(N) 时间内解决。AC Code

BZOJ3622 已经没有什么好害怕的了

记糖果为 A_{1\cdots n}，药片为 B_{1\cdots n}。那么当 n,k 不同奇偶时无解，否则应当有 \frac{n+k}{2} 个位置满足 A_i>B_i，剩下的为 A_i<B_i。

下面记 k 为原来的 \frac{n+k}{2}。仍然是钦定 k 个位置，让这 k 个位置满足 A_i>B_i，想想怎么算方案数。发现不是很好用组合数算。

对于每个 A_i 我们算出来 C_i 表示 B 中 <A_i 的元素个数，将 A 从小到大排序，那么 C 序列递增且前面的 C 是后面的子集。

现在相当于要钦定 k 个位置选出 C_i 所代表的集合中的数且不能重复，剩下的随便选。

这个可以 DP 做，f(i,j) 表示前 i 个数配了 j 组时的方案数，那么 f(i,j)=f(i-1,j)+f(i-1,j-1)\times (C_j-(j-1))。

那么记 F_j=(n-j)!f(n,j)，答案就是 F 做一个二项式反演。于是这题就做完了，时间复杂度 O(n^2)。AC Code

JSOI2011 分特产

设 f(k) 为钦定 k 个人，他们分不到特产，剩下的人随便分，的方案数。那么答案就是 f 做一个二项式反演。

注意到 f(k) 实际上等价于给 n-k 个人分特产，不过可以有人没分到的方案数。

然后我们发现其实每种特产大概是独立的，那么给 m 个人分的时候答案就是

\prod_{i=1}^n\binom{a_i+m-1}{m-1}

我们对每个 m 把这东西算一遍就得到了 f，再反演就得到了 g。暴力算是 O(n^2) 的，已经可以通过。AC Code

实际上我们拆拆式子发现

\prod_{i=1}^n\binom{a_i+m-1}{m-1}=\prod_{i=1}^n\dfrac{(a_i+m-1)!}{a_i!(m-1)!}=\prod_{i=1}^n\dfrac{(a_i+m-2)!}{a_i!}\prod_{i=1}^n(a_i+m-1)\times \dfrac{1}{((m-1)!)^n}

我们发现只要能快速算出来 \prod (a_i+m-1) 就能递推。

设 F(x)=\prod(a_i+x)，那么可以分治 NTT 在 O(n\log ^2n) 的时间内得到 F，再 O(n\log ^2n) 做个多点求值，就得到了 O(n\log ^2n) 的算法。

NOI Online#2 提高组游戏

和 BZOJ3622 比较相似，考虑钦定 k 个位置，让这 k 个位置不是平局。我们将 A 的点染黑，B 的点染白。

现在相当于要选出 k 组互为祖孙关系的点对，求方案数。

这个可以用树形 DP 做，设 f(u,j) 为只考虑点 u 子树内的点，配 j 对的方案。

设 X_u 为 u 子树中白点个数，Y_u 为 u 子树中黑点个数，转移时考虑看 u 是否配对：

如果 u 不配对，那么直接把 u 的儿子的背包合并上来即可。
如果 u 配对，不妨设 u 是黑点，此时相当于子树中已经配了 j-1 对，那么 u 还有 X_u-(j-1) 种选择。因此将子树内 j-1 的背包合并上来再乘 (X_u-(j-1)) 即可。

那么我们可以 O(n^2) 算出来钦定 k 个位置的方案数，再 O(n^2) 反演一遍就完事了。AC Code

JSOI2015 染色问题

我们发现这题有三个限制。如果没有限制，那么答案就是 (C+1)^{n\times m}。

考虑设 f(i,j,k) 为钦定某 i 行，某 j 列全都空着，某 k 种颜色不选的方案数，那么 f(i,j,k)=(C-k+1)^{(n-i)\times (m-j)}\binom{n}{i}\binom{m}{j}\binom{C}{k}。

然后设 g(i,j,k) 为恰好 i 行 j 列 k 种颜色不选的方案数，有

f(i,j,k)=\sum_{x=i}^n\sum_{y=j}^m\sum_{z=k}^C\binom{x}{i}\binom{y}{j}\binom{z}{k}g(i,j,k)

发现是个三维的二项式反演，我们猜想

g(i,j,k)=\sum_{x=i}^n\sum_{y=j}^m\sum_{z=k}^C(-1)^{x+y+z-i-j-k}\binom{x}{i}\binom{y}{j}\binom{z}{k}f(i,j,k)

从容斥的角度考虑一下，感觉很对。直接做要带个 \log，不过不难做到 O(n^3)。AC Code

注意到其实三维中有一维可以直接算出来，所以不难优化到 O(n^2)。。。（我是傻子qaq

ABC266G Yet Another RGB Sequence

考虑钦定 i 个位置是 RG，那么还剩 R-i 个 R，G-i 个 G，B 个 B，方案数可以随便算。

于是就做完了，果然是板子题。

ABC217G Groups

我们考虑对非空这个条件做容斥。

具体来说把 1,2,\cdots N 分成 M 组，第 i 组中每个数都 \bmod M=i，设其大小为 C_i。

现在我们钦定其中某 i 组是空的，那么

f(i)=\prod_{j=0}^{M-1}\binom{k-i}{C_j}\times C_j!

那么答案可以直接通过二项式反演 O(M) 得到。

我们发现如果直接算的话需要算 N 次，每次都要 O(NM)，过不去。

但是可以发现本质不同的 k-i 其实只有 O(N) 组，因此直接处理出来所有的

F_x=\prod_{j=0}^{M-1}\binom{x}{C_j}\times C_j!

然后算 f(i) 就只需要查表了。总的复杂度为 O(NM)。AC Code

CF285E Positions in Permutation

设 f(i,j,0/1,0/1) 表示由 1\cdots i 构成的排列，有 j 个 good position 的方案数，后面两个 0/1 的含义待会再说。

我们考虑这样由 1,2,\cdots,i 的排列构建一个 1,2,\cdots,i+1 的排列：先把最后一位放上 i+1，再将最后一位和前面的某一位 swap 一下。

这样一来，我们只需要分别计算出来有多少种 swap 可以使得 good position 的数量 +1/-1/ 不变即可。

我们考虑 x 满足 a_x=i 以及 a_i 的值是什么。进行一个分类：

如果 i+1 和某个 x,i 之外的数 swap 了，那么如果原本那个位置是 good position，j 需要减一；否则不变。
如果和 x 进行 swap，那么 i+1 会是一个 good position，但是 x 那个位置原本是不是 good position 我们不知道，因此需要记录一下。
如果和 i 进行 swap，那么 i 会是一个 good position，但是这个位置原本是不是 good position 我们也不知道，需要记录一下。

因此状态就是：

转移分类讨论一下就行了。等等说好的二项式反演在哪里呢

我们思考一下容斥做法：直接钦定某 k 个位置为 good position，剩下的位置的方案数我们默认为 1。

我们发现这个东西类似于一个匹配：

我们把黑边拉直，然后相当于要从 n-1 条边中选出 k 条互不相邻的边。简单插板得到 f(k)=\binom{n-k}{k}。

那么我们的 F 就是 f 和自己卷一下，答案就是

G(m)=\sum_{i=m}^n(-1)^{i-m}F(k)

暴力 O(n^2) 计算已经可以通过本题。注意到 F 是个卷积，因此可以做到 O(n\log n)。

CF997C Sky Full of Stars

相信做了之前那么多题之后这题已经非常简单了。。。

考虑钦定某 k 列是同一种颜色，剩下的随便填，并且需要满足每一行都不是同一种颜色。有

f(k)=\begin{cases}(3^n-3)^n&,k=0\\\binom{n}{k}\times\left(3\times \left(3^{n-k}-1\right)^n+\left(3^k-3\right)\times 3^{n(n-k)}\right)&,k>0\end{cases}

然后二项式反演再做个小容斥就完事了。时间复杂度 O(n\log n) 或 O(n)。AC Code

CF995F Cowmpany Cowmpensation

这题有个拉格朗日插值的做法，不过我们可以用容斥过掉它。

我们发现虽然值域很大，但是实际上用到的数只可能有 O(n) 种。

设 g(i) 为恰好用 [1,i] 中每个数填好，并且每种数至少出现一次，的方案数，那么答案就是 \sum_{x}\binom{D}{x}g(x)。

这是因为我们可以把一种方案离散化掉，那么离散化到 [1,x] 的方案数恰为 \binom{D}{x}。

我们发现至少出现一次看着就很容斥，因此可以求出来 f(i) 表示只用 [1,i] 中的数，随便填（可以有某些数没有用到）的方案数。

那么 g 其实就是 f 二项式反演一下，于是就可以 O(n^2) 直接算了。代码懒得写了，，先坑着