Link
Description
计数有多少个 \(n\) 个点 \(m\) 条边的无向图满足恰好有 \(k\) 个点的度数为 \(1\)。
Solution
容易发现度数为 \(1\) 的点只有两种状态:和另一个度数为 \(1\) 的点相连;和一个大连通块连边。于是想到对这两种情况进行分类讨论,枚举两种情况点的个数。
令 \(F(x)\) 表示钦定 \(x\) 个点度数为 \(1\) 的可重方案数,那么
\[F(x)=\binom{n}{x} \sum_{i=0}^{\lfloor \frac{x}{2}\rfloor} \binom{x}{2i}\frac{(2i)!}{i!2^i}(n-x)^{x-2i} \binom{(n-x)(n-x-1)/2}{m-x+i} \]反演一下即为答案
\[G(k)=\sum_{x=k}^n (-1)^x \binom{x}{k} F(x) \]#include<stdio.h>
#define ll long long
#define N 2500007
#define Mod 998244353
int n,m,k;
ll fac[N],inv[N],pw[N],pw_[N];
inline ll qpow(ll x,ll y){
ll ret=1,cnt=0;
while(y>=(1ll<<cnt)){
if(y&(1ll<<cnt)) ret=(ret*x)%Mod;
x=(x*x)%Mod,cnt++;
}
return ret;
}
ll C(int x,int y){return x<y? 0:fac[x]*inv[y]%Mod*inv[x-y]%Mod;}
int main(){
scanf("%d%d%d",&n,&m,&k);
fac[0]=pw[0]=pw_[0]=1;
for(int i=1;i<N;i++) fac[i]=fac[i-1]*i%Mod,pw[i]=(pw[i-1]<<1)%Mod;
inv[N-1]=qpow(fac[N-1],Mod-2),pw[N-1]=qpow(pw[N-1],Mod-2);
for(int i=N-2;~i;i--) inv[i]=inv[i+1]*(i+1)%Mod,pw[i]=pw[i+1]*2%Mod;
ll ans=0;
for(int r=k,op=1;r<=n;r++,op=-op){
ll ret=(op*C(r,k)*C(n,r)%Mod+Mod)%Mod;
ll tmp=0; int M=(n-r)*(n-r-1)/2;
for(int i=1;i<=r;i++) pw_[i]=(pw_[i-1]*(n-r))%Mod;
for(int i=0;i<=r/2;i++)
tmp=(tmp+C(r,2*i)*fac[2*i]%Mod*pw[i]%Mod*inv[i]%Mod*C(M,m-r+i)%Mod*pw_[r-2*i]%Mod)%Mod;
ans=(ans+tmp*ret%Mod)%Mod;
}
printf("%lld",ans);
}