前言

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

`void prufer(){
    int p=1,lf;
    for(int i=1;in;i++) deg[i]++,deg[fa[i]]++;
    while(deg[p]!=1) p++;
    lf=p;
    for(int i=1;in-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

`void invprufer(){
    int p=1,lf;
    for(int i=1;in-1;i++)deg[pru[i]]++;
    for(int i=1;in;i++) deg[i]++;
    while(deg[p]!=1) p++;
    lf=p;
    for(int i=1;in-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
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

`#include
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\left(\genfrac{}{}{0ex}{}{i}{x}\right)\left(\genfrac{}{}{0ex}{}{j}{y}\right)g_{i,j}⟺g_{0,0}=\sum _{i=0}^n\sum _{j=0}^n(-1{)}^{i+j}{f}_{i,j}$$

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

• 当 $i,j\ne 0$ 时：$f_{i,j}=\left(\genfrac{}{}{0ex}{}{n}{i}\right)\left(\genfrac{}{}{0ex}{}{n}{j}\right)·3^{(n-i)(n-j)+1}$

• 当 $ij=0,i+j\ne 0$ 时：$f_{i,0}=f_{0,i}=\left(\genfrac{}{}{0ex}{}{n}{i}\right)·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\left(\genfrac{}{}{0ex}{}{n}{i}\right)(-1{)}^i{3}^{-in}\left((1-3^{i-n}{)}^n-1\right)-2·3^{n^2}\left((1-3^{1-n}{)}^n-1\right)$$

代码：

C++

#include
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=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

`#include
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;in;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;in;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{)}^{\left|T\right|}·N(T)$$

其中 $N\left(T\right)$ 表示：将 $T$ 中的边强制变成 `解释：

• 对于一条内向边 $u\text{[PARSE ERROR: Ampersand]}gt;v$：

• 不放入 $T$：这条边被拆掉，$u$ 和 $v$ 分属不同连通块，彼此无大小约束。

• 放入 $T$：这条边被强制变成 `

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

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

记组合数 $C=\left(\genfrac{}{}{0ex}{}{s{z}_u+s{z}_v}{s{z}_u}\right)$，表示将两棵子树的拓扑序交错合并的方案数（内部顺序不变，从总位置中选 $s{z}_u$ 个给 $u$ 子树的节点）。

• 外向边 ``：两种选择对应容斥 $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
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 t[N];

void init(){
    inv[1]=1;
    for(int i=2;i>n;
    init();
    for(int u=2;u>v>>w;
        t[v].push_back({u,w=='>'});
    }
    dfs(1);
    for(int i=1;i

`#include
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;
};
vectornode> t[N];

void init(){
    inv[1]=1;
    for(int i=2;in;i++) (inv[i]=(mod-mod/i)*inv[mod%i])%=mod;
    C[0][0]=1;
    for(int i=1;in;i++){
        C[i][0]=1;
        for(int j=1;ji;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;isiz[u];i++) for(int j=1;jsiz[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;isiz[u];i++){
            dp[u][i]=f[i];
            f[i]=0;
        }
    }
    for(int i=1;isiz[u];i++) (dp[u][i]*=inv[i])%=mod;
}

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