二项式反演
证明
我们设 \(g(x)\) 为任意 \(x\) 个集合的交集的大小， \(f(x)\) 表示任意 \(x\) 个集合补集的交集大小。
首先有 (组合数学6.2)
\[|\overline{S_1}\cap\overline{ S_2}\cap...\cap \overline{S_{n-1}}\cap \overline{S_n}|=|U|-|{S_1}|-|{S_2}|-...+(-1)^n\times |{S_1}\cap {S_2}\cap...\cap{S_{n-1}}\cap {S_n}|=\sum\limits_{i=0}^n(-1)^i\dbinom{n}{i}g(i) \]将补集看成原集，将原集看成补集，就有
\[|S_1\cap S_2\cap...\cap S_{n-1}\cap S_n|=|U|-|\overline{S_1}|-|\overline{S_2}|-...+(-1)^n\times |\overline{S_1}\cap \overline{S_2}\cap...\cap\overline{S_{n-1}}\cap \overline{S_n}|=\sum\limits_{i=0}^n(-1)^i\dbinom{n}{i}f(i) \]可以知道
\[g(n)=|S_1\cap S_2\cap ...\cap S_{n-1}\cap S_n| \]\[f(n)=|\overline{S_1}\cap\overline{ S_2}\cap...\cap \overline{S_{n-1}}\cap \overline{S_n}| \]所以就有反演基本形式：
\[g(n)=\sum\limits_{i=0}^n(-1)^i\dbinom{n}{i}f(i)\Longleftrightarrow f(n)=\sum\limits_{i=0}^n(-1)^i\dbinom{n}{i}g(i) \]另 \(h(x)=(-1)^xf(x)\)
那么就可以得到最常用的形式
\[g(n)=\sum\limits_{i=0}^n\dbinom{n}{i}f(i)\Longleftrightarrow \frac{h(n)}{(-1)^n}=\sum\limits_{i=0}^n(-1)^i\dbinom{n}{i}h(i) \]\[g(n)=\sum\limits_{i=0}^n\dbinom{n}{i}f(i)\Longleftrightarrow h(n)=\sum\limits_{i=0}^n(-1)^{n-i}\dbinom{n}{i}h(i) \]形式
形式零
\[f[n]=\sum_{i=0}^n(-1)^i*C^i_n*g[i] \Leftrightarrow g[n]=\sum_{i=0}^n(-1)^i*C^i_n*f[i] \]形式一（适用于设至多存在）
\[f(n)=\sum\limits_{i=0}^n{n\choose i}g(i)\Leftrightarrow g(n)=\sum\limits_{i=0}^n(-1)^{n-i}{n\choose i}f(i) \]形式二（适用于设至少存在）
\[f(n)=\sum\limits_{i=n}^m{i\choose n}g(i)\Leftrightarrow g(n)=\sum\limits_{i=n}^m(-1)^{i-n}{i\choose n}f(i) \]组合意义
记 \(g(n)\) 表示 "至少选 \(n\) 个" \(f(n)\) 表示 "恰好选 \(n\) 个",则对于任意的 \(i≥x\) ,\(f(i)\) 在 \(g(x)\) 中被计算了 \(\dbinom{i}{n}\) 次，故 \(g(x)=\sum_{i=x}^{n}\) ，其中 \(n\) 是数目上界。
例题
集合计数
题目大意
一个有 \(n\) 个元素的集合有 \(2^n\) 个不同子集（包含空集），现在要在这 \(2^n\) 个集合中取出至少一个集合，使得它们的交集的元素个数为 \(k\) ，求取法的方案数模 \(10^9+7\) 。
题解
通过思考列出式子 \({C^i_n}(2^{2^{n-i}}-1)\) 。即钦定 \(i\) 个交集元素，则包含这 \(i\) 个的集合有 \(2^{n-i}\) 个；每个集合可选可不选，但不能都不选，由此可得此方案数。
接下来考虑上式与所求的关系：设 \(f(i)\) 表示钦定交集元素为某 \(i\) 个的方案数，\(g(i)\) 表示交集元素恰好为 \(i\) 个的方案数，则
\({C^k_n}(2^{2^{n-k}}-1)=f(k)=\sum\limits_{i=k}^n{i\choose k}g(i)\)
通过二项式反演求出 \(g(k)=\sum\limits_{i=k}^n(-1)^{i-k}{i\choose k}f(i)=\sum\limits_{i=k}^n(-1)^{i-k}{i\choose k}{n\choose i}(2^{2^{n-i}}-1)\)
使用一些预处理手段，时间复杂度 \(O(n)\) 。
这里对于 \(2^{2^{n-i}}\) 取模，这里可以进行预处理，定义 \(base[i]\) 数组，\(base[i]=2^{2^{n-i}}\)
，则 $base[i]=base[i-1]^2 mod $ \(p\) 即可。
Another Filling the Grid
对于一行合法的话，答案就是 \(k^n-(k-1)^n\)。那么考虑加上列，那么我们设 \(g_i\) 表示至少有 \(i\) 列不合法，相当于下界的限制，那么就有 \(g_i={n \choose i} ((k-1)^i k^(n-i)-(k-1)^n)^n\)。
那么二项式反演有 \(Ans=\sum_{i=0}^{n} (-1)^{i-0} {i \choose 0}g_i\)。
code
// Another Filling the Grid
#include<bits/stdc++.h>
#define int long long
const int mod=1e9+7;
const int N=300;
int qpow(int x,int p){
int ans=1;
while(p){
if(p&1) ans=(ans*x)%mod;
x=(x*x)%mod;
p>>=1;
}
return ans;
}
int g[N+5];
int fac[N+5],inv[N+5];
void init(){
fac[0]=inv[0]=1;
for(int i=1;i<=N;i++) fac[i]=fac[i-1]*i%mod;
inv[N]=qpow(fac[N],mod-2);
for(int i=N-1;i>=1;i--) inv[i]=inv[i+1]*(i+1)%mod;
}
int C(int x,int y){
return fac[x]*inv[y]%mod*inv[x-y]%mod;
}
signed main(){
int n,k;
scanf("%lld%lld",&n,&k);
init();
for(int i=0;i<=n;i++){
g[i]=C(n,i)*qpow((qpow(k,n-i)*qpow(k-1,i)%mod-qpow(k-1,n)+mod)%mod,n)%mod;
}
int ans=0;
for(int i=0;i<=n;i++){
int tmp=((i)%2 ? -1: 1);
ans=(ans+tmp*C(i,0)*g[i]%mod+2*mod)%mod;
}
printf("%lld",ans);
}
[JLOI2016] 成绩比较
考虑将这个分成两个部分考虑
1.计算在n-1个人中选出k个，被B神碾压的方案数并且对于剩下的n-1-k个人，计算有多少种方案来合法分配每一个人、每一门科目的得分状况。这里，得分状况定义为是比B神高，还是比B神低或相等。
2.已知每一门科目的得分状况，计算对于给定的满分，有多少种分配分数的方案。
对于第一部分
我们设 \(g(p)\) 表示至少有 \(p\) 个被碾压，考虑每一门科目有 \(r_i-1\) 个人比他高，这些人来自 \(n-p-1\) 个人中，那么就有 \(g(p)={n \choose p} \prod_{i=1}^{m} {r_i-1 \choose n-p-1}\)。
然后设 \(f(p)\) 表示恰好有 \(p\) 个被碾压，根据二项式定理就有 \(f(p)=\sum_{x=p}^{n} (-1)^{x-p} {x \choose p}g(x)\)。
那么这一部分答案就是 \(f(k)\)。
对于第二部分
我们考虑 \(G(u,a,b)\) 表示取值范围位 \(u\)，有 \(a\) 个比他大， \(b\) 个小于等于他，那么可以枚举他的成绩计算。
因为 \(u\) 的范围太大，所以我们考虑枚举有几种就可以，就是乘上组合数 \({u \choose t}\)，我们发现你并不能取到 \(t\) 种颜色，所以我们再一次进行二项式反演，这回设 \(h(t)\) 表示至多有 \(t\) 种颜色，然后求 \(p(t)\) 表示恰好有 \(t\) 种颜色。
code
// 成绩比较
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
const int N=1005;
int U[N+5],R[N+5];
int fac[N+5],inv[N+5];
int g[N+5],h[N+5];
int qpow(int x,int p){
int ans=1;
while(p){
if(p&1) ans=(ans*x)%mod;
x=(x*x)%mod;
p>>=1;
}
return ans;
}
void init(){
inv[0]=fac[0]=1;
for(int i=1;i<=N;i++) fac[i]=fac[i-1]*i%mod;
inv[N]=qpow(fac[N],mod-2);
for(int i=N-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
}
int C(int x,int y){
if(x<y) return 0;
return fac[x]*inv[y]%mod*inv[x-y]%mod;
}
int CC(int x,int y){
int ans=1;
for(int i=x-y+1;i<=x;i++) ans=ans*i%mod;
for(int i=1;i<=y;i++) ans=ans*qpow(i,mod-2)%mod;
return ans;
}
int G(int u,int a,int b){ // > : a // <= : b
int ans=0;
for(int x=1;x<=u;x++){
int w=qpow(u-x,a)*qpow(x,b)%mod;
ans=(ans+w)%mod;
}
return ans;
}
signed main(){
int n,m,k;
scanf("%lld%lld%lld",&n,&m,&k);
for(int i=1;i<=m;i++) scanf("%lld",&U[i]);
for(int i=1;i<=m;i++) scanf("%lld",&R[i]);
init();
// 比自己高的一定是不被碾压的，比自己低的不一定是被碾压的
for(int p=1;p<=n;p++){
g[p]=C(n-1,p); // 至少有 p 个被碾压的
for(int i=1;i<=m;i++){
g[p]=g[p]*C(n-p-1,R[i]-1)%mod;
}
}
int fx=0;
for(int i=k;i<=n;i++){
int tmp=((i-k)%2 ? -1 : 1);
fx=(fx+tmp*C(i,k)%mod*g[i]%mod+mod)%mod;
}
int fy=1;
for(int i=1;i<=m;i++){
int tp=min(n,U[i]);
for(int t=1;t<=tp;t++){
h[t]=G(t,R[i]-1,n-R[i])%mod;//*C(U[i],t)
}
int cnt=0;
for(int t=1;t<=tp;t++){
int sum=0;
for(int j=1;j<=t;j++){
int tmp=((t-j)%2 ? -1 : 1);
int kl=tmp*C(t,j)%mod*h[j]%mod;
sum=(sum+kl+mod)%mod;
}
cnt=(cnt+sum*CC(U[i],t)%mod+mod)%mod;
}
fy=fy*cnt%mod;
}
printf("%lld",fx*fy%mod);
}
多元二项式反演公式
如果满足
\[g(n_1,n_2,\cdots,n_m)=\sum\limits_{k_i=0}^{n_i}\prod^m_{i=1}\dbinom{n_i}{k_i}f(k_1,k_2,\cdots,k_m) \]那么就有
\[f(n_1,n_2,\cdots,n_m)=\sum_{k_i=0}^{n_i}\prod_{i=1}^m(-1)^{n_i-k_i}\dbinom{ n_i }{k_i}g(k_1,k_2,\cdots,k_m)\]Sky Full of Stars
设 \(g_{i,j}\) 表示至少有 \(i\) 行 \(j\) 列同一个颜色，\(f_{i,j}\) 表示恰好有 \(i\) 行 \(j\) 列同一个颜色。
那么有 \(g_{i,j}=\sum_{x=i}^{n} \sum_{y=j}^{n} {x \choose i}{y \choose j} f_{i,j}\) 那么有
\[f_{i,j}=\sum_{x=i}^{n} \sum_{y=j}^{n} (-1)^{x-i} {x \choose i}(-1)^{y-j}{y \choose j} g_{i,j} \]发现答案其实是 \(3^{n^2} - f_{0,0}\)，所以只考虑如何求 \(f_{0,0}\)。
考虑 \(g_{i,j}\) 的答案，我们此时必须要考虑零的情况：
-
假如都不为 0
\(g_{i,j}=3 {n \choose i} {n \choose j} 3^{(n-i)(n-j)}\)
-
有一维为 0
\(g_{i,0}=3^i {n \choose i} 3^{(n-i)n}\)
-
两维均为 0
\(g_{i,0}=3^{n^2}\)
所以我们要分开考虑，先考虑第一部分，我们合并同类项得：
\[f_{1,1}=3^{n^2+1} \sum_{x=1}^{n} (-1)^{x} {n \choose x} 3^{-nx} \sum_{y=1}^{n} (-1)^{y} {n \choose y} 3^{-ny} 3^{xy} \]问题在于 \(3^{xy}\) 怎么处理，我们可以考虑将后面的合并得到 \(\sum_{y=1}^{n} {n \choose y} (-3)^{(x-n)y}\)，感觉可以补一位进行二项式定理得到 \((1-3^{x-n})^n-1\)。
最后就是
\[f_{1,1}=3^{n^2+1} \sum_{x=1}^{n} (-1)^{x} {n \choose x} 3^{-nx} (1-3^{x-n})^n-1 \]然后再算一下第二部分，让一个是然后结果乘二就行
其实还可以化成二项式形式，也就是 \(3^{n^2} \sum_{i=1}^{n} {n \choose i} (-3^{1-n})^i\)
那么就有 \(3^{n^2} [(1-3^{1-n})^n-1]\)
然后再算第三部分。
code
// Sky Full of Stars
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
const int mod=998244353;
int fac[N+5],inv[N];
int qpow(int x,int p){
p=(p%(mod-1)+mod-1)%(mod-1);
x=(x%mod+mod)%mod;
int ans=1;
while(p){
if(p&1) ans=(ans*x)%mod;
x=(x*x)%mod;
p>>=1;
}
return ans;
}
void init(){
fac[0]=inv[0]=1;
for(int i=1;i<=N;i++) fac[i]=fac[i-1]*i%mod;
inv[N]=qpow(fac[N],mod-2);
for(int i=N-1;i>=1;i--) inv[i]=inv[i+1]*(i+1)%mod;
}
int C(int x,int y){
return fac[x]*inv[y]%mod*inv[x-y]%mod;
}
int base[N];
signed main(){
init();
int n;
scanf("%lld",&n);
int ans=0;
for(int i=1;i<=n;i++){
int w=(i%2 ? -1 : 1);
w=w*C(n,i)%mod*qpow(3,-i*n)%mod*(qpow(1-qpow(3,-n+i),n)-1+mod)%mod;
ans=(ans+w+mod)%mod;
}
ans=ans*qpow(3,n*n+1)%mod;
for(int i=1;i<=n;i++){
int w=(i%2 ? -1 : 1);
w=w*C(n,i)%mod*qpow(3,n*(n-i))%mod*qpow(3,i)%mod;
ans=(ans+w*2%mod+mod)%mod;
}
printf("%lld",(mod-ans)%mod);
}