前言
B 班太难了，回 C 班了。。。
二项式反演
二项式反演经常被使用于那些求恰好为 $n$ 个的方案数的问题。
常用形式：
$g_n$ 表示至多 $n$ 个的方案，$f_n$ 表示恰好 $n$ 个的方案：
$g_n$ 表示至少 $n$ 个的方案，$f_n$ 表示恰好 $n$ 个的方案：
Prufer 序列
看图示：
题单
文艺计算姬
可以从 Prufer 序列的角度计算，因为 Prufer 序列最后会剩下一条边，这条边肯定是连接二分图左右两边的，因此左右两边每一边分别删掉了 $n-1$ 和 $m-1$ 个点，每删一边的点就会把另一边的点记录到 Prufer 序列中，所以左右两边的贡献乘一起为 $n^{m-1}\times m^{n-1}$。
代码：
#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)
$$
代码：
#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;
}
Comments NOTHING