多步容斥
多步容斥是指，对于 \(n\) 个集合 \(A_1,A_2,\cdots,A_n\)，有
\[|A_1 \cup A_2 \cdots \cup A_n| = \sum \limits_{1 \leq i \leq n}|A_i|-\sum \limits _{1 \leq i< j \leq n}|A_i \cap A_j| + \sum \limits_{1 \leq i < j < k \leq n}|A_i\cap A_j \cap A_k| +(-1)^{n-1} |A_1 \cap A_2 \cdots \cap A_n| \]考虑证明，对于一个被 \(m\) 个集合包含的元素，对等号左侧的贡献是 \(1\)，对等号右边的贡献是
\[\sum \limits_{i=1}^{m} \dbinom{m}{i}(-1)^{i-1} = - \sum \limits_{i=1}^{m} \dbinom{m}{i}(-1)^i = -\left((1-1)^m - \dbinom{m}{0}\right)=-(0-1)=1 \]证毕。
记 \(A_i^c\) 表示 \(i\) 的补集，注意集合的并的补集等于补集的交集，于是有
\[|A_1^c \cap A_2^c \cdots \cap A_n^c| =|S|- \sum \limits_{1 \leq i \leq n}|A_i|-\sum \limits _{1 \leq i< j \leq n}|A_i \cap A_j| + \sum \limits_{1 \leq i < j < k \leq n}|A_i\cap A_j \cap A_k| +(-1)^{n-1} |A_1 \cap A_2 \cdots \cap A_n| \]补集的补集就是原集，于是
\[|A_1 \cap A_2 \cdots \cap A_n| =|S|- \sum \limits_{1 \leq i \leq n}|A_i^c|-\sum \limits _{1 \leq i< j \leq n}|A_i^c \cap A_j^c| + \sum \limits_{1 \leq i < j < k \leq n}|A_i^c\cap A_j^c \cap A_k^c| +(-1)^{n-1} |A_1^c \cap A_2^c \cdots \cap A_n^c| \]这就是多步容斥。对于集合 \(S\)，其中的元素有 \(n\) 种不同的属性，第 \(i\) 种属性记作 \(P_i\)，满足 \(P_i\) 的元素构成的集合记作 \(A_i\)，它表明如下两点：
- 具有性质 \(P_1,P_2,\cdots,P_n\) 中至少一个的元素数量可以通过对同时具有某些性质的元素数量进行容斥得到。
- 具有全部性质 \(P_1,P_2,\cdots,P_n\) 的元素数量可以通过对同时不具有某些性质的元素数量进行容斥得到。
二项式反演
二项式反演 · 形式零
\[F(n) = \sum \limits_{i=m}^{n} (-1)^i \dbinom{n}{i} G(i) \Leftrightarrow G(n) = \sum \limits_{i=m}^{n} (-1)^i \dbinom{n}{i} F(i) \]其中 \(m\) 为常数。
考虑证明，我们直接将 \(G(i)\) 带到左边 \(F(n)\) 的定义式中，看化简完后等不等于 \(F(n)\) 即可。
\[F(n) = \sum \limits_{i=m}^{n} (-1)^i \dbinom{n}{i} G(i) = \sum \limits_{i=m}^{n} (-1)^i \dbinom{n}{i} \sum \limits_{j=m}^i (-1)^j \dbinom{i}{j} F(j) \]\[=\sum \limits_{j=m}^{n} (-1)^jF(j)\sum \limits_{i=j}^{n} (-1)^i \dbinom{n}{i} \dbinom{i}{j} \]\[=\sum \limits_{j=m}^{n} (-1)^jF(j)\sum \limits_{i=j}^{n} (-1)^i \dbinom{n}{j} \dbinom{n-j}{i-j} \]\[=\sum \limits_{j=m}^{n} \dbinom{n}{j}F(j)\sum \limits_{i=j}^{n} (-1)^{i+j} \dbinom{n-j}{i-j} \]\[=\sum \limits_{j=m}^{n} \dbinom{n}{j}F(j)\sum \limits_{i=0}^{n-j} (-1)^{i+2j} \dbinom{n-j}{i} \]\[=\sum \limits_{j=m}^{n} \dbinom{n}{j}F(j)\sum \limits_{i=m}^{n-j} (-1)^{i} \dbinom{n-j}{i} \]\[=\sum \limits_{j=m}^{n} \dbinom{n}{j}F(j)(1-1)^{n-j} \]\[=F(n) \]另一侧的证明同理。
当然，我们也可以通过多步容斥的角度来理解它。考虑一种特殊的情况，\(A_1,A_2,\cdots,A_n\) 中任意 \(k\) 个集合的交大小都是 \(F(k)\)，任意 \(k\) 个集合补集的并大小都是 \(G(k)\)，此时有
\[F(n) = \sum \limits_{i=0}^{n} (-1)^i \dbinom{n}{i} G(i) \]和
\[G(n) = \sum \limits_{i=0}^{n} (-1)^i \dbinom{n}{i} F(i) \]二项式反演 · 形式一
\[F(n) = \sum \limits_{i=m}^{n}\dbinom{n}{i} G(i) \Leftrightarrow G(n) = \sum \limits_{i=m}^{n} (-1)^{n-i} \dbinom{n}{i} F(i) \]在形式零中，令 \(G'(i) = (-1)^i G(i)\)，就得到了
\[F(n) = \sum \limits_{i=m}^{n}\dbinom{n}{i} G'(i) \Leftrightarrow G'(n) = \sum \limits_{i=m}^{n} (-1)^{n+i} \dbinom{n}{i} F(i) \]注意到 \((-1)^{n+i} = (-1)^{n-i}\)，于是得证。
二项式反演 · 形式二
\[F(n) = \sum \limits_{i=n}^{m} \dbinom{i}{n} G(i) \Leftrightarrow G(n) = \sum \limits_{i=n}^{m} (-1)^{i-n} \dbinom{i}{n}F(i) \]完全是形式一的对称版本。考虑证明，右侧带入左侧，
\[F(n) = \sum \limits_{i=n}^{m} \dbinom{i}{n} \sum \limits_{j=i}^{m} (-1)^{j-i} \dbinom{j}{i} F(j) \]\[= \sum \limits_{j=n}^{m} F(j) \sum \limits_{i=n}^{j} (-1)^{j-i} \dbinom{j}{i} \dbinom{i}{n} \]\[= \sum \limits_{j=n}^{m} F(j) \sum \limits_{i=n}^{j} (-1)^{j-i} \dbinom{j}{n} \dbinom{j-n}{i-n} \]\[= \sum \limits_{j=n}^{m} \dbinom{j}{n} F(j) \sum \limits_{i=n}^{j} (-1)^{j-i} \dbinom{j-n}{i-n} \]考虑用 \(i-n\) 替换 \(i\)，得
\[= \sum \limits_{j=n}^{m} \dbinom{j}{n} F(j) \sum \limits_{i=0}^{j-n} (-1)^{j-n-i} \dbinom{j-n}{i} \]\[= \sum \limits_{j=n}^{m} \dbinom{j}{n} F(j) (1-1)^{j-n} \]\[=F(n) \]至此，我们得到了二项式反演的三种常见形式。
计数转化
我们往往会遇到一类问题，要计算从 \(n\) 个中恰好选 \(k\) 个时的答案。这有时候会十分困难，因此我们先计算从 \(n\) 个中钦定 \(k\) 个选择（剩下 \(n-k\) 个可选可不选）时的答案 \(F(k)\)（这往往很简单），然后二项式反演求出恰好选 \(k\) 个的答案 \(G(k)\)。
一个简单的例子，计数 \(n\) 位 \(01\) 串中恰有 \(k\) 位为 \(1\) 的串个数。一方面，根据组合知识这就等于 \(\dbinom{n}{k}\)，但我们可以稍微绕一些远路，来了解二项式反演的基本用法。我们注意到，\(F(k)=\dbinom{n}{k}2^{n-k}\)，这是因为钦定 \(k\) 个位置为 \(1\)，剩下的 \(n-k\) 个位置可以随意选择。
接下来，我们考虑 \(G\) 对 \(F\) 的贡献。每个 \(k \leq x \leq n\) 的 \(G(x)\) 对 \(F(k)\) 的贡献是 \(\dbinom{x}{k} G(x)\)，因为 \(G(x)\) 中每种方案恰好选了 \(x\) 个 \(1\)，而一种方案有 \(\dbinom{x}{k}\) 种被 \(F(k)\) 钦点到的方案，因此
\[F(k) = \sum \limits_{x=k}^{n} \dbinom{x}{k} G(x) \]根据二项式反演，
\[G(k) = \sum \limits_{x=k}^{n} (-1)^{x-k} \dbinom{x}{k} F(x) \]\[= \sum \limits_{x=k}^{n} (-1)^{x-k} \dbinom{x}{k} \dbinom{n}{x} 2^{n-x} \]\[= \sum \limits_{x=k}^{n} (-1)^{x-k} \dbinom{n}{k} \dbinom{n-k}{x-k} 2^{n-x} \]\[= \dbinom{n}{k} \sum \limits_{x=k}^{n} (-1)^{x-k} \dbinom{n-k}{x-k} 2^{n-x} \]\[= \dbinom{n}{k}\sum \limits_{x=0}^{n-k} \dbinom{n-k}{x} (-1)^{x} 2^{n-(x+k)} \]\[= \dbinom{n}{k}(-1+2)^{n-k} = \dbinom{n}{k} \]需要注意的是，\(F(k)\) 计算的并不是选了至少 \(k\) 个的答案，如果是这样，那直接用 \(F(k)\) 减去 \(F(k+1)\) 就可以得到 \(G(k)\) 了。钦定 \(k\) 个的答案和前者有本质区别，因为对于同一种方案 \(F(k)\) 会重复计算多次，而前者显然只计算一次。
例如，钦定两位 \(01\) 串的某一位为 \(1\)，一共有 \(\dbinom{2}{1}\times2^{2-1}=4\) 种方案，钦定高位时方案为 \(10,11\)，低位时方案为 \(01,11\)，\(11\) 就被计算了两次。但正是这个性质保证了 \(G\) 可以被 \(F\) 二项式反演出来。
例 1 BZOJ 2839 集合计数
题意
一个有 \(n\) 个元素的集合有 \(2^n\) 个不同子集（包含空集），现在要在这 \(2^n\) 个集合中取出若干集合（至少一个），使得它们的交集的元素个数为 \(k\)，求取法的方案数。答案对 \(10^9+7\) 取模。
\(1 \leq n \leq 10^6\)
题解
考虑钦定 \(k\) 个交集元素，此时有 \(2^{n-k}\) 个集合包含这 \(k\) 个元素，因此有 \(F(k) = \dbinom{n}{k} (2^{2^{n-k}}-1)\) 种取法，\(-1\) 是因为至少选择一个集合。
显然有
\[F(k) = \sum \limits_{x=k}^{n} \dbinom{x}{k} G(x) \]从而
\[G(k) = \sum \limits_{x=k}^{n} (-1)^{x-k} \dbinom{x}{k} \dbinom{n}{x} (2^{2^{n-x}}-1) \]注意到 \(2^{2^i}\) 也可以递推预处理出来，于是复杂度 \(O(n)\)。当然我一开始只会分块光速幂。
例 2 Luogu P4859 已经没什么好害怕的了
题意
给定长度为 \(n\) 的序列 \(a,b\)，保证这 \(2n\) 个数都不相同。你可以重排序列 \(b\)，设重排后有 \(x\) 对 \(a_i>b_i\)，\(y\) 对 \(a_i<b_i\)，求 \(x-y=k\) 的方案数。
\(1 \leq n \leq 2000,0 \leq k \leq n\)
题解
考虑二元一次方程
\[\begin{cases}x-y = k \\ x+y = n\end{cases} \]解得 \(x=\dfrac{n+k}{2}\)，也就是说，如果 \(n+k\) 不为偶数，那么无解。接下来，我们要讨论的是重排后有 \(\dfrac{n+k}{2}\) 对 \(a_i>b_i\) 的方案数。
考虑钦定若干对 \(a_i>b_i\) 的方案数。显然把 \(a\) 排序之后比较好做，于是我们先排序。
令 \(dp_{i,j}\) 表示前 \(i\) 个数钦定 \(j\) 对 \(a_i>b_i\) 的方案数，\(c_i\) 表示 \(b\) 中比 \(a_i\) 小的数的数量。有 \(dp_{i,j} = dp_{i-1,j}+(c_i-(j-1))dp_{i-1,j-1}\)，因为 \(dp_{i-1,j-1}\) 中每一种方案都用掉了 \(j-1\) 个比 \(a_i\) 小的 \(b_x\)，于是 \(a_i\) 还能选的 \(b_x\) 就只剩下 \(c_i-(j-1)\) 个了。
设 \(F(i)\) 表示钦定 \(j\) 对 \(a_i>b_i\)，剩下部分可以任意排列的方案数，\(G(i)\) 表示答案。有 \(F(i)=(n-i)!dp_{n,i}\)，二项式反演即可求出 \(G(i)\)。
# include <bits/stdc++.h>
const int N=2010,INF=0x3f3f3f3f,MOD=1e9+9;
int n,k;
int fac[N],inv[N],a[N],b[N],c[N];
int dp[N][N];
int f[N],g[N];
inline int read(void){
int res,f=1;
char c;
while((c=getchar())<'0'||c>'9')
if(c=='-') f=-1;
res=c-48;
while((c=getchar())>='0'&&c<='9')
res=res*10+c-48;
return res*f;
}
inline int qpow(int d,int p){
int ans=1;
while(p){
if(p&1) ans=1ll*ans*d%MOD;
d=1ll*d*d%MOD,p>>=1;
}
return ans;
}
inline int C(int n,int r){
return 1ll*fac[n]*inv[r]%MOD*inv[n-r]%MOD;
}
inline int mip(int x){
return (x%2)?-1:1;
}
int main(void){
n=read(),k=read();
if((n+k)%2){
printf("0");
return 0;
}
fac[0]=inv[0]=1;
for(int i=1;i<=n;++i) fac[i]=1ll*fac[i-1]*i%MOD;
inv[n]=qpow(fac[n],MOD-2);
for(int i=n-1;i;--i) inv[i]=1ll*inv[i+1]*(i+1)%MOD;
for(int i=1;i<=n;++i) a[i]=read();
for(int i=1;i<=n;++i) b[i]=read();
std::sort(a+1,a+1+n),std::sort(b+1,b+1+n);
for(int i=1;i<=n;++i) c[i]=std::upper_bound(b+1,b+1+n,a[i])-b-1;
dp[0][0]=1;
for(int i=1;i<=n;++i)
for(int j=0;j<=c[i];++j) dp[i][j]=(dp[i-1][j]+1ll*dp[i-1][j-1]*(c[i]-j+1)%MOD)%MOD;
for(int i=0;i<=n;++i) g[i]=1ll*dp[n][i]*fac[n-i]%MOD; // 代码里的 g[i] 就是 F(i)
int id=(n+k)/2,ans=0;
for(int i=id;i<=n;++i){ // 二项式反演
ans=((ans+1ll*mip(i-id)*C(i,id)%MOD*g[i]%MOD)%MOD+MOD)%MOD;
}
printf("%d",ans);
return 0;
}
高维二项式反演
二项式反演可以拓展到高维。以形式一为例，
\[f_{N,M} = \sum \limits_{i=n}^{N} \sum \limits_{j=m}^{M} \dbinom{N}{i} \dbinom{M}{j} g_{i,j} \]\[\Leftrightarrow g_{N,M} = \sum \limits_{i=n}^{N} \sum \limits_{j=m}^{M} (-1)^{(N-i)+(M-j)}\dbinom{N}{i} \dbinom{M}{j} f_{i,j} \]考虑证明。首先，
\[f_{N,M} = \sum \limits_{i=n}^{N} \dbinom{N}{i} (\sum \limits_{j=m}^{M} \dbinom{M}{j} g_{i,j}) \]令 \(F(i) = f_{i,M}\)，\(G(i) = \sum \limits_{j=m}^M \dbinom{M}{j} g_{i,j}\)，那么
\[F(N) = \sum \limits_{i=n}^{N} \dbinom{N}{i} G(i) \]二项式反演，
\[G(N) = \sum \limits_{i=n}^{N} (-1)^{N-i} \dbinom{N}{i} F(i) \]展开得
\[\sum \limits_{j=m}^M \dbinom{M}{j} g_{N,j} = \sum \limits_{i=n}^N (-1)^{N-i} \dbinom{N}{i} f_{i,M} \]再二项式反演一次，设 \(F(i) = \sum \limits_{j=n}^N (-1)^{N-j} \dbinom{N}{j} f_{j,i}\)，\(G(i) = g_{N,i}\)，那么
\[F(M) = \sum \limits_{j=m}^{M} \dbinom{M}{j} G(i) \]从而
\[G(M) = \sum \limits_{j=m}^{M} (-1)^{M-j} \dbinom{M}{j} F(j) \]展开得
\[g_{N,M} = \sum \limits_{j=m}^{M} (-1)^{M-j} \dbinom{M}{j} \left( \sum \limits_{i=n}^{N} (-1)^{N-i} \dbinom{N}{i} f_{i,j}\right) \]\[g_{N,M} = \sum \limits_{i=n}^{N} \sum \limits_{j=m}^{M} (-1)^{(N-i)+(M-j)}\dbinom{N}{i} \dbinom{M}{j} f_{i,j} \]注意到上面证明过程中每一步都是可逆的，因此上面的两个式子等价。
形式零和形式二同样可证成立，而且可以拓展到更高维。考虑我们做的工作，就是把 \(g_{i,j}\) 从求和号中变出来，每二项式反演一次 \(g_{i,j}\) 的求和号就少一个，同时 \(f_{i,j}\) 外面就会多一个求和号。
例 3 Codeforces 997C Sky Full of Stars
题意
用三种颜色给 \(n \times n\) 的格子染色，要求至少要有一行或一列颜色相同，求方案数。
\(1 \leq n \leq 10^6\)
题解
设 \(F(i,j)\) 表示钦定 \(i\) 行 \(j\) 列相同的方案数，\(G(i,j)\) 表示恰好 \(i\) 行 \(j\) 列相同的方案数。
考虑高维二项式反演的形式二，
\[F(x,y) = \sum \limits_{i=x}^{n} \sum \limits_{j=y}^m \dbinom{i}{x} \dbinom{j}{y} G(i,j) \]\[\Leftrightarrow G(x,y) = \sum \limits_{i=x}^{n} \sum \limits_{j=y}^m (-1)^{(i-x)+(j-y)} \dbinom{i}{x} \dbinom{j}{y} F(i,j) \]而在本题中，答案就是总方案数减去 \(G(0,0)\)。如果 \(F(i,j)\) 易求，那么我们就可以反演出 \(G(0,0)\)。
注意到：
-
\(F(0,0) = 3^{n^2}\)
-
对于 \(i>0\)，\(F(i,0) = F(0,i) = \dbinom{n}{i} 3^i \times 3^{(n-i)n}\) ，即选 \(i\) 行或 \(i\) 列颜色相同，剩下的随意，当然这些行或列之间颜色不一定要相同。
-
对于 \(i,j > 0\)，\(F(i,j)= \dbinom{n}{i} \dbinom{n}{j} 3 \times 3^{(n-i)(n-j)}\)，此时这 \(i\) 行 \(j\) 列颜色必须全部相同，只有 \(3\) 种方案，剩下的随意。
而
\[G(0,0) = \sum \limits_{i=0}^{n} \sum \limits_{j=0}^{n} (-1)^{i+j} F(i,j) \]根据前面的讨论，对 \(F\) 分三个部分计算贡献。
-
\(i=j=0\)
贡献为 \(3^{n^2}\)。
-
\(i,j\) 恰有一个不为 \(0\)
注意到贡献对称，于是直接计算 \(i\) 不等于 \(0\) 的部分再乘以 \(2\) 即可。
\[\sum \limits_{i=1}^n (-1)^i F(i,0) = \sum \limits_{i=1}^{n} (-1)^i \dbinom{n}{i} 3^{n^2-in+i} \]\[=3^{n^2} \sum \limits_{i=1}^{n} (-1)^i \dbinom{n}{i} 3^{i(1-n)} \]\[=3^{n^2} \sum \limits_{i=1}^{n} \dbinom{n}{i} (-3^{1-n})^{i} \]\[=3^{n^2} \left((1-3^{1-n})^n -1\right) \] -
\(i,j\) 都不为 \(0\)
\[\sum \limits_{i=1}^n\sum \limits_{j=1}^{n} (-1)^{i+j} \dbinom{n}{i} \dbinom{n}{j} 3 \times 3^{(n-i)(n-j)} \]\[=\sum \limits_{i=1}^n(-1)^{i} \dbinom{n}{i} \sum \limits_{j=1}^{n} (-1)^j \dbinom{n}{j} \times 3^{n^2+1-(i+j)n+ij} \]\[=3^{n^2+1} \sum \limits_{i=1}^n(-1)^{i} 3^{-in} \dbinom{n}{i} \sum \limits_{j=1}^{n} (-1)^j \dbinom{n}{j} 3^{-jn} \times 3^{ij} \]考虑把 \(3^{ij}\) 项吸进去，用上面第三步到倒数第二步的套路，
\[3^{n^2+1} \sum \limits_{i=1}^n(-1)^{i} 3^{-in} \dbinom{n}{i} \sum \limits_{j=1}^{n} (-1)^j \dbinom{n}{j} 3^{j(i-n)} \]\[=3^{n^2+1} \sum \limits_{i=1}^n(-1)^{i} 3^{-in} \dbinom{n}{i} \sum \limits_{j=1}^{n} (-1)^j \dbinom{n}{j} 3^{j(i-n)} \]\[=3^{n^2+1} \sum \limits_{i=1}^n(-1)^{i} 3^{-in} \dbinom{n}{i} \sum \limits_{j=1}^{n} \dbinom{n}{j}(-3^{i-n})^j \]\[=3^{n^2+1} \sum \limits_{i=1}^n(-1)^{i} 3^{-in} \dbinom{n}{i} \left((1-3^{i-n})^n-1\right) \]快速幂计算即可，复杂度 \(O(n \log n)\)。
最后答案是 \(3^{n^2}\) 减掉所有贡献，第一部分减完了就没了，对后两部分贡献取反即可。注意指数对 \(\varphi(p) = 998244352\) 取模。
# include <bits/stdc++.h>
const int N=1000010,MAXN=1e6,INF=0x3f3f3f3f,MOD=998244353,PMOD=998244352;
int fac[N],inv[N];
int n;
inline int read(void){
int res,f=1;
char c;
while((c=getchar())<'0'||c>'9')
if(c=='-')f=-1;
res=c-48;
while((c=getchar())>='0'&&c<='9')
res=res*10+c-48;
return res*f;
}
inline int qpow(int d,int p){
int ans=1;
for(;p;d=1ll*d*d%MOD,p>>=1) (p&1)&&(ans=1ll*ans*d%MOD);
return ans;
}
inline void init(void){
fac[0]=inv[0]=1;
for(int i=1;i<=MAXN;++i) fac[i]=1ll*fac[i-1]*i%MOD;
inv[MAXN]=qpow(fac[MAXN],MOD-2);
for(int i=MAXN-1;i;--i) inv[i]=1ll*inv[i+1]*(i+1)%MOD;
return;
}
inline int C(int n,int m){
return 1ll*fac[n]*inv[m]%MOD*inv[n-m]%MOD;
}
int main(void){
init();
n=read();
int ans=2ll*qpow(3,1ll*n*n%PMOD)*(qpow((1+MOD-qpow(3,(1+PMOD-n)%PMOD)),n)-1)%MOD,sum=0;
if(ans<0) ans+=MOD;
for(int i=1;i<=n;++i){
sum=(sum+1ll*((i%2)?-1:1)*qpow(3,(PMOD-1ll*i*n%PMOD))*C(n,i)%MOD*(qpow((1+MOD-qpow(3,(i+PMOD-n)%PMOD)),n)-1)%MOD)%MOD;
}
ans=(ans+1ll*qpow(3,(1ll*n*n+1)%PMOD)*sum%MOD)%MOD;
if(ans<0) ans+=MOD;
printf("%d",(MOD-ans)%MOD);
return 0;
}