二项式反演学习笔记

Bryan1676 · 2026-08-18 19:35:05 · 算法·理论

二项式反演学习笔记

简述二项式反演

对于两个函数 f(x),g(x)，有：

证明如下（左推右）。

先给出一个引理：

证明见提示：（可以自己先试着推一推）

:::info[证明] 考虑左右两边的组合意义，左边代表先从 j 个里选出 i 个，再从 i 个里选出 x 个，也就是将 x 个选了两次，i-x 个选了一次。

我们有：

故原命题得证，Q.E.D!

相似的，我们也有：

推广到二维，我们有：

证明考虑令函数 h(x,y)=\sum_{j=1}^y \binom{y}{j} g(i,j) 然后对 g 和 h 与 h 和 f 做两次二项式反演。

应用场景

当我们要求的问题具有限制：某种操作或选择恰好做 x 次的方案数时，如果直接做很难做，可以转化为要求该操作至多（少）做了 i 次，然后二项式反演即可，具体见例题。

例题

T1 [JSOI2015] 染色问题

给一个 n \times m 的矩形染色，共有 c 种颜色，每个格子可染可不染，要求每行每列至少有一个格子被染色，每种颜色至少使用一次。

直接做显然是不好做的，令 f(i,j,k) 表示恰好染了 i 行，j 列，使用了 k 种颜色，考虑对他进行二项式反演。

记 g(i,j,k) 表示恰好染了 i 行，j 列，使用了至多 k 种颜色，显然的，我们有：

故

此时依然不好做，考虑继续反演，记 h(i,j,k) 表示至多染了 i 行，j 列，使用了至多 k 种颜色的方案数，我们有。

故：

显然的，我们有：

此时其实可以直接做了，\mathcal O(nmc) 的复杂度完全可以接受，但还能继续优化。

故：

复杂度（默认 n,m,c 同阶） \mathcal O(n^2\log n)。

:::success[code]

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define PII pair<int,int>
#define fi first
#define se second
#define mk make_pair
#define pb push_back
#define ivoid inline void
ivoid wsp(int x){
    cout<<x<<" ";
}
ivoid wln(int x){
    cout<<x<<"\n";
}
ivoid wstr(string s){
    cout<<s<<"\n";
}
#define cout cerr

const int maxn=410;
const int mod=1e9+7;
int n,m,c,f[maxn],g[maxn],inv[maxn],fac[maxn],po[2]={1,-1};

void init(){
    inv[0]=inv[1]=fac[0]=fac[1]=1;
    for(int i=2;i<=400;i++){
        inv[i]=inv[mod%i]*(mod-(mod/i))%mod;
        fac[i]=fac[i-1]*i%mod;
    }
    for(int i=2;i<=400;i++) inv[i]=inv[i]*inv[i-1]%mod;
}

int C(int a,int b){
    if(a>b||a<0) return 0;
    else if(a==0||a==b) return 1;
    else return fac[b]*inv[a]%mod*inv[b-a]%mod;
}

int qp(int a,int b){
    int ans=1;
    while(b){
        if(b&1) ans=(ans*a)%mod;
        a=a*a%mod,b>>=1;
    }
    return ans;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m>>c;
    init();
    int ans=0;
    for(int i=0;i<=c;i++){
        for(int j=0;j<=m;j++){
            ans=(ans+((C(i,c)*C(j,m)%mod*qp((qp(i+1,j)-1+mod)%mod,n))%mod*po[(c+m-i-j)&1])+mod)%mod;
        }
    }
    wln(ans);
    return 0;
}

:::

T2 Sky Full of Stars

我们发现至少一行和至少一列这个限制很不好做，考虑转化成非零行且零列然后容斥。

记 f_{i,j} 表示至少有 i 行 j 列同色的情况数，显然我们有：

二三四式直接暴力即可，无需优化，考虑一式如何优化，我们有：

直接计算即可，复杂度 \mathcal O(n \log n)。

:::success[code]

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define PII pair<int,int>
#define fi first
#define se second
#define mk make_pair
#define pb push_back
#define ivoid inline void
ivoid wsp(int x){
    cout<<x<<" ";
}
ivoid wln(int x){
    cout<<x<<"\n";
}
ivoid wstr(string s){
    cout<<s<<"\n";
}
#define cout cerr

const int maxn=1e6+10;
const int mod=998244353;
int n,sum1=0,sum2=0,ans=0;
int inv[maxn],fac[maxn];

void init(){
    inv[0]=inv[1]=fac[0]=fac[1]=1;
    for(int i=2;i<=1e6;i++){
        inv[i]=inv[mod%i]*(mod-(mod/i))%mod;
        fac[i]=fac[i-1]*i%mod;
    }
    for(int i=2;i<=1e6;i++) inv[i]=inv[i]*inv[i-1]%mod;
}

int C(int a,int b){
    if(a>b||a<0) return 0;
    else if(a==0||a==b) return 1;
    else return fac[b]*inv[a]%mod*inv[b-a]%mod;
}

int qp(int a,int b){
    int ans=1;b%=(mod-1);
    while(b){
        if(b&1) ans=(ans*a)%mod;
        a=a*a%mod,b>>=1;
    }
    return ans%mod;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n;
    init();
    int c=-1;
    for(int i=1;i<=n;i++){
        sum1=(sum1+((c+mod)%mod*C(i,n)%mod*qp(qp(3,i*n),mod-2)%mod*(qp((1-qp(qp(3,n-i),mod-2)+mod)%mod,n)-1+mod)%mod)%mod)%mod;
        c=-c;
    }
    sum1=sum1*qp(3,n*n+1)%mod;
//  cout<<sum1<<"\n";
    c=-1;
    for(int i=1;i<=n;i++){
        sum2=(sum2+((c+mod)%mod*qp(3,i)%mod*C(i,n)%mod*qp(3,n*(n-i))%mod))%mod;
        c=-c;
    }
    sum2*=2;
    wln(mod-((sum1+sum2)%mod));
    return 0;
}

:::

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

考虑如何钦定一些数使得他们被选择，很自然的想到 dp，首先，将所有数放到一个序列上从小到大排序，记 dp_{i,j} 表示前 i 个数钦定了 j 个 a，指向左侧比它小的数，显然有转移：