考虑计算钦定$m$条割边的方案数$f_m$.最后再二项式反演还原。
$f_m$就是缩点后$m+1$个点的树,其中每个点是一个连通图(总点数为$n$)的方案数(如果不用二项式反演就是边双连通图数了,难整)
记$i$个点的连通图数量为$g_i$,有
$$
f_m=\frac{1}{(m+1)!}\sum_{\sum A=n,|A|=m+1} \binom{n}{a_1,a_2…a_{m+1}}n^{m-1}\prod_i a_ig_{a_i}
$$
这里用到一个经典结论:$m$个连通块,大小分别为$a_1,a_2…a_n$,连成的有标号树数量为$(\sum a_i)^{m-2}\prod a_i$,可参见「WC2019」数树
这样加入一个大小为$x$的块的贡献看成$\frac{xg_{x}}{x!}$,直接dp就行了。
注意到$m\ge n-1$时$f_m=0$,所以复杂度是$O(n^3)$.
实际上转移式子是卷积,所以理论上也可以MTT优化到$O(n^2\log n)$.听说利用某些多项式科技可以做到更好?
const int MAXN = 511,mod = 1e9+7;
int f[MAXN][MAXN],g[MAXN],all[MAXN],tp[MAXN];
ll fac[MAXN],inv[MAXN];
ll C(int n,int m){return fac[n]*inv[m]%mod*inv[n-m]%mod;}
ll Qpow(ll a,ll p)
{
ll res=1;
while(p){if(p&1)res=res*a%mod;a=a*a%mod,p>>=1;}
return res;
}
void init(int n)
{
fac[0]=inv[0]=1;
for(int i=1;i<=n;++i)fac[i]=fac[i-1]*i%mod;
inv[n]=Qpow(fac[n],mod-2);
for(int i=n-1;i;--i)inv[i]=inv[i+1]*(i+1)%mod;
all[0]=1;
for(int i=1;i<=n;++i)all[i]=Qpow(2,i*(i-1)/2);
//Also,G = ln All
for(int i=1;i<=n;++i)
{
g[i]=all[i];
for(int j=1;j<i;++j)g[i]=(g[i]-C(i-1,j-1)*g[j]%mod*all[i-j])%mod;
}
}
int main()
{
int n=read(),m=read(),invn=Qpow(n,mod-2);
init(n);
f[0][0]=1;
for(int i=1;i<=n;++i)
for(int j=i;j<=n;++j)
for(int x=1;x<=j;++x)
f[i][j]=(f[i][j]+ll(f[i-1][j-x])*inv[x-1]%mod*g[x])%mod;
for(int i=0;i<n;++i)
{
tp[i]=f[i+1][n]*Qpow(n,i)%mod*invn%mod*fac[n]%mod*inv[i+1]%mod;
}
int ans=0;
for(int i=0;i<=min(n-1,m);++i)
{
int cur=0;
for(int j=i;j<=n;++j)
if((j-i)&1)cur=(cur-C(j,i)*tp[j])%mod;
else cur=(cur+C(j,i)*tp[j])%mod;
ans=(ans+cur)%mod;
}
printf("%d\n",(ans+mod)%mod);
return 0;
}
欸,我也是这个想法(
牛逼!!!!!!!!!天不生你万爷爷!!!!!!!!!!!!OI 万古如长夜!!!!!!!!!!!!111
嘿嘿,科技改变生活