ZR 集训 Day15 – 组合数学

ooliver 发布于 2026-07-31 447 次阅读 OI

AI 摘要

从“恰好”到“至多/至少”，二项式反演帮你巧妙转换；一棵树与 Prufer 序列的神秘对应，竟能推出 `n^{m-1} × m^{n-1}`？容斥、拓扑序、组合计数——C 班也能玩转的硬核套路，看完直呼原来如此！

前言

B 班太难了，回 C 班了。。。

二项式反演

二项式反演经常被使用于那些求恰好为 $n$ 个的方案数的问题。

常用形式：

$g_n$ 表示至多 $n$ 个的方案，$f_n$ 表示恰好 $n$ 个的方案：

gn=∑i=0n(ni)fi⟺fn=∑i=0n(−1)n−i(ni)gig_n = \sum_{i = 0}^{n} {n \choose i}f_i\iff f_n = \sum_{i = 0}^{n} (-1)^{n-i}{n \choose i} g_i

$g_n$ 表示至少 $n$ 个的方案，$f_n$ 表示恰好 $n$ 个的方案：

gn=∑i=nm(in)fi⟺fn=∑i=nm(−1)i−n(in)gig_n=\sum_{i=n}^m {i \choose n} f_i \iff f_n=\sum_{i=n}^m (-1)^{i-n} {i \choose n} g_i

Prufer 序列

看图示：

代码：

C++
void prufer(){
    int p=1,lf;
    for(int i=1;i<n;i++) deg[i]++,deg[fa[i]]++;
    while(deg[p]!=1) p++;
    lf=p;
    for(int i=1;i<n-1;i++){
        pru[i]=fa[lf],deg[fa[lf]]--;
        if(deg[fa[lf]]==1&&fa[lf]<p) lf=fa[lf];
        else{
            p++;
            while(deg[p]!=1) p++;
            lf=p;
        }
    }
}

代码：

C++
void invprufer(){
    int p=1,lf;
    for(int i=1;i<n-1;i++)deg[pru[i]]++;
    for(int i=1;i<=n;i++) deg[i]++;
    while(deg[p]!=1) p++;
    lf=p;
    for(int i=1;i<n-1;i++){
        fa[lf]=pru[i],deg[fa[lf]]--;
        if(deg[fa[lf]]==1&&fa[lf]<p) lf=fa[lf];
        else{
            p++;
            while(deg[p]!=1) p++;
            lf=p;
        }
    }
    fa[lf]=n;
}

题单

文艺计算姬

可以从 Prufer 序列的角度计算，因为 Prufer 序列最后会剩下一条边，这条边肯定是连接二分图左右两边的，因此左右两边每一边分别删掉了 $n-1$ 和 $m-1$ 个点，每删一边的点就会把另一边的点记录到 Prufer 序列中，所以左右两边的贡献乘一起为 $n^{m-1}\times m^{n-1}$。

代码：

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

#define int long long
int n,m,q;

__int128 qpow(__int128 x,__int128 y){
    __int128 res=1;
    while(y){
        if(y&1) (res*=x)%=q;
        (x*=x)%=q,y>>=1;
    }
    return res;
}

signed main(){
    cin>>n>>m>>q;
    cout<<(int)(((__int128)qpow(n,m-1)*(__int128)qpow(m,n-1))%q);
    return 0;
}

CF997C Sky Full of Stars

二维二项式反演题。

设 $f_{i,j}$ 为至少有 $i$ 行 $j$ 列颜色相同的方案数，$g_{i,j}$ 为恰好有 $i$ 行 $j$ 列颜色相同的方案数。

有：

$$
f_{x,y} = \sum_{i=x}^n \sum_{j=y}^n \binom{i}{x}\binom{j}{y} g_{i,j} \iff g_{0,0} = \sum_{i=0}^n \sum_{j=0}^n (-1)^{i+j} f_{i,j}
$$

分类讨论 $f_{i,j}$ 的取值：

  • 当 $i, j \neq 0$ 时：$f_{i,j} = \binom{n}{i}\binom{n}{j} \cdot 3^{(n-i)(n-j)+1}$
  • 当 $ij = 0, i+j \neq 0$ 时：$f_{i,0} = f_{0,i} = \binom{n}{i} \cdot 3^{i+n(n-i)}$
  • 当 $i = j = 0$ 时：$f_{0,0} = 3^{n^2}$

$$
\begin{aligned}
g_{0,0} &= \sum_{i=1}^n \sum_{j=1}^n (-1)^{i+j} f_{i,j} + 2 \sum_{i=1}^n (-1)^i f_{i,0} + f_{0,0} \\
&= \sum_{i=1}^n \sum_{j=1}^n (-1)^{i+j} \binom{n}{i}\binom{n}{j} \cdot 3^{(n-i)(n-j)+1} + 2 \sum_{i=1}^n (-1)^i \binom{n}{i} \cdot 3^{i+n(n-i)} + 3^{n^2} \\
&= 3^{n^2+1} \sum_{i=1}^n \binom{n}{i} (-1)^i 3^{-in} \left( (1 - 3^{i-n})^n - 1 \right) + 2 \cdot 3^{n^2} \left( (1 - 3^{1-n})^n - 1 \right) + 3^{n^2}
\end{aligned}
$$

代入 $ans = 3^{n^2} - g_{0,0}$，抵消 $3^{n^2}$ 后得到最终公式：

$$
ans = -3^{n^2+1} \sum_{i=1}^n \binom{n}{i} (-1)^i 3^{-in} \left( (1 - 3^{i-n})^n - 1 \right) - 2 \cdot 3^{n^2} \left( (1 - 3^{1-n})^n - 1 \right)
$$

代码：

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

#define int long long
const int N=1e6+5;
const int mod=998244353;
int n,ans,a,b;
int jie[N],inv[N];

int qpow(int x,int y){
    int res=1;
    ((x%=mod)+=mod)%=mod;
    while(y){
        if(y&1) (res*=x)%=mod;
        (x*=x)%=mod,y>>=1;
    }
    return res;
}

void init(){
    jie[0]=1;
    for(int i=1;i<=n;i++) (jie[i]=jie[i-1]*i)%=mod;
    inv[n]=qpow(jie[n],mod-2);
    for(int i=n-1;i>=0;i--) (inv[i]=inv[i+1]*(i+1))%=mod;
}

int chose(int n,int m){
    return jie[n]*inv[n-m]%mod*inv[m]%mod;
}

signed main(){
    cin>>n;
    init();
    for(int i=1;i<=n;i++){
        int c=chose(n,i),
            d=qpow(qpow(3,i*n),mod-2),
            e=qpow(qpow(3,n-i),mod-2),
            f=qpow(mod-e+1,n)-1,
            num=c*d%mod*f%mod;
        if(i&1) (a-=num)%=mod;
        else (a+=num)%=mod;
    }
    (a*=qpow(3,n*n+1))%=mod;
    int c=qpow(qpow(3,n-1),mod-2),
        d=(qpow(mod-c+1,n)-1)%mod;
    b=d*2%mod*qpow(3,n*n)%mod;
    ans=(a+b)%mod;
    cout<<(mod-ans)%mod;
    return 0;
}

P6086 【模板】Prüfer（Prufer）序列

模板，上面有代码，这里不赘述了。

P12639 [UOI 2020] Topological Sorting of a Tree

考虑容斥：

容斥公式：
$$\text{答案} = \sum_{T \subseteq S} (-1)^{|T|} \cdot N(T)$$

其中 $N(T)$ 表示：将 $T$ 中的边强制变成 <，其余不在 $T$ 中的边全部拆掉（无约束） 的方案数。

解释：

  • 对于一条内向边 $u > v$：
  • 不放入 $T$：这条边被拆掉，$u$ 和 $v$ 分属不同连通块，彼此无大小约束。
  • 放入 $T$：这条边被强制变成 <，$u$ 和 $v$ 在同一连通块内，且 $u < v$，同时贡献 $-1$ 的系数。
  • 每条边独立选择，容斥系数相乘。所有选择组合的带权和恰好等于满足原约束的方案数。

设 $f_{u,i}$ 为在 $u$ 子树中，$u$ 所在连通块大小为 $i$ 的带容斥系数方案数之和。

从叶子向上合并，枚举当前 $u$ 的连通块大小 $i$ 和子节点 $v$ 的连通块大小 $j$。

记组合数 $C = \binom{sz_u + sz_v}{sz_u}$，表示将两棵子树的拓扑序交错合并的方案数（内部顺序不变，从总位置中选 $sz_u$ 个给 $u$ 子树的节点）。

  • 外向边 <：必须合并连通块
    $f'_{u,i+j}= f'_{u,i+j}+f_{u,i} \times f_{v,j} \times C$
  • 内向边 >：两种选择对应容斥
    $f'_{u,i} = f'_{u,i} +f_{u,i} \times f_{v,j} \times C \quad $
    $f'_{u,i+j} = f'_{u,i+j}-(f_{u,i} \times f_{v,j} \times C) \quad $

合并完所有子节点后，根据拓扑序公式除以连通块大小：$f_{u,i} \leftarrow f_{u,i} \times i^{-1}$

最终答案为：$\text{ans} = \sum_{i=1}^n f_{1,i}$

代码（这题三倍经验）：

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

#define int long long
const int N=3005;
const int mod=1e9+7;
int n,ans;
int dp[N][N],C[N][N],f[N],siz[N],inv[N];
struct node{
    int v;
    bool w;
};
vector<node> t[N];

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

void dfs(int u){
    dp[u][1]=siz[u]=1;
    for(auto[v,w]:t[u]){
        dfs(v);
        for(int i=1;i<=siz[u];i++) for(int j=1;j<=siz[v];j++){
            if(w){
                (f[i]+=dp[u][i]*dp[v][j]%mod*C[siz[u]+siz[v]][siz[v]])%=mod;
                ((f[i+j]-=dp[u][i]*dp[v][j]%mod*C[siz[u]+siz[v]][siz[v]]%mod)+=mod)%=mod;
            }
            else (f[i+j]+=dp[u][i]*dp[v][j]%mod*C[siz[u]+siz[v]][siz[v]])%=mod;
        }
        siz[u]+=siz[v];
        for(int i=1;i<=siz[u];i++){
            dp[u][i]=f[i];
            f[i]=0;
        }
    }
    for(int i=1;i<=siz[u];i++) (dp[u][i]*=inv[i])%=mod;
}

signed main(){
    cin>>n;
    init();
    for(int u=2;u<=n;u++){
        int v;
        char w;
        cin>>v>>w;
        t[v].push_back({u,w=='>'});
    }
    dfs(1);
    for(int i=1;i<=n;i++) (ans+=dp[1][i])%=mod;
    cout<<ans;
    return 0;
}