7.10考试-解题报告
i207M
2019-07-10 14:47:58
T1打表题。
T3**题。
## T2
zzt做法：
枚举联通块个数，斯特林反演，记录联通块内的边数和m
，贡献为$\sum_i(m/n^2)^i$
ztb神仙做法：
设$f[n][m]$表示n个点加了m条边，联通的概率。写出式子来，把$c^i$用$e^{cx}$代替，然后发现生成函数的基本单位是$\sum_ia_ie^{ix}$（欧拉GF？开关GF？），我们用这个卷积出答案多项式即可。
都是$O(n^4)$
```cpp
signed main()
{
in(n),in(md);
fac[0]=1;
for(ri i=1;i<=n;++i) fac[i]=(LL)fac[i-1]*i%md;
ifac[n]=qpow(fac[n],md-2);
for(ri i=n;i>=1;--i) ifac[i-1]=(LL)ifac[i]*i%md;
g[0][0]=1;
for(ri i=1;i<=n;++i)
for(ri k=0,mk=i*i;k<=mk;++k)
for(ri h=1;h<=i&&h*h<=k;++h)
{
inc(g[i][k],md-(LL)g[i-h][k-h*h]*C(i,h)%md);
}
int ans=0,iv=qpow(n*n,md-2);
for(ri k=0,mk=n*n,t;k<=mk;++k)
{
t=0;
for(ri h=1;h<=n&&h*h<=k;++h)
inc(t,md-(LL)g[n-h][k-h*h]*C(n-1,h-1)%md);
t=(LL)t*qpow(1-(LL)k*iv%md+md,md-2)%md;
inc(ans,t);
}
out(ans);
return 0;
}
```