一周一博客二专题计划
题面
n 个点的简单 (无重边无自环) 有标号无向连通图数目。
看着就很典
思路
设\(f(n)\)为n点连通图数目。设\(g(n)\)为n点不一定联通图数目，显然直接枚举每条边是否存在，\(g(n)=2^{\frac{n*(n-1)}{2}}\)
\[g(n)=\sum_{i=1}^{n} \left( \begin{array}{c} n-1 \\ i-1 \end{array} \right) f(i)g(n-i)
\]
可看作枚举1号节点所在连通块的大小，组合数是从其他n-1个点中选出与1同联通块的点
很多博客都是推完式子然后发现卷积形式。其实应该看到多项式相乘，考虑卷积求解，化式子时尽量将i相关放在一起，n-i相关放在一起
而组合数上的n-1明显要拆出来
\[\frac{g(n)}{(n-1)!}=\sum_{i=1}^{n} \frac{f(i)}{(i-1)!} \frac{g(n-i)}{(n-i)!}
\]
很明显，设
\[a_i=\frac{f(i+1)}{i!}
\]
\[b_j=\frac{2^{\frac{j*(j-1)}{2}}}{j!}
\]
\[c_k=\frac{2^{\frac{k*(k+1)}{2}}}{k!}
\]
有
\[c_k=\sum_{i+j=k}a_ib_j
\]
NTT的式子已经出来了，不同的是此时我们已知\(c\)而想求\(a\)，直接对\(b\)多项式求逆\(a=c*invb\)
答案\(f(n)=a_{n-1}*(n-1)!\)
代码
#include<bits/stdc++.h>
using namespace std;
const int MAX=2.7e5+10;
#define int long long
const int mod=1004535809;
int n,bl,bc,rev[MAX],a[MAX],b[MAX],f[MAX],g[MAX];
int fac[MAX],inv[MAX],c[MAX];
inline int read(){
int x=0,f=1;char c=getchar();
while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^'0');c=getchar();}
return x*f;
}
inline int power(int a,int b){
int res=1;
while(b){
if(b&1) res=res*a%mod;
a=a*a%mod;b>>=1;
}return res;
}inline void NTT(int*,int,int);
void solve(int);
inline void work(int len){
bl=1;bc=0;
while(bl<=len) bl<<=1,++bc;
for(int i=0;i<bl;++i)
rev[i]=(rev[i>>1]>>1)|((i&1)<<bc-1);
}
signed main(){
n=read();fac[0]=1;
for(int i=1;i<=n;++i) fac[i]=fac[i-1]*i%mod;
inv[n]=power(fac[n],mod-2);
for(int i=n-1;i>=0;--i) inv[i]=inv[i+1]*(i+1)%mod;
f[0]=1;c[0]=1;
for(int i=1;i<n;++i){
f[i]=power(2,(i-1)*i/2)*inv[i]%mod;
c[i]=power(2,i*(i+1)/2)*inv[i]%mod;
}
solve(n);work(n<<1);
NTT(g,bl,1);NTT(c,bl,1);
for(int i=0;i<bl;++i) g[i]=g[i]*c[i]%mod;
NTT(g,bl,-1);printf("%d",g[n-1]*fac[n-1]%mod);
}
void solve(int len){
if(len==1){g[0]=power(f[0],mod-2);return;}
solve(len+1>>1);work(len+n);
memcpy(a,f,sizeof(a));memset(b,0,sizeof(b));
for(int i=0;i<len+1>>1;++i) b[i]=g[i];
NTT(a,bl,1);NTT(b,bl,1);
for(int i=0;i<bl;++i) g[i]=b[i]*((2-a[i]*b[i]%mod+mod)%mod)%mod;
NTT(g,bl,-1);
}inline void NTT(int *a,int n,int op){
for(int i=0;i<n;++i)
if(i<rev[i]) swap(a[i],a[rev[i]]);
for(int i=1;i<n;i<<=1){
int wn=power(3,(op*(mod-1)/(i<<1)+mod-1)%(mod-1));
for(int j=0;j<n;j+=i<<1){
int w=1;
for(int k=0;k<i;++k){
int x=a[j+k],y=a[j+k+i]*w%mod;
a[j+k]=(x+y)%mod;a[j+k+i]=(x-y+mod)%mod;
w=w*wn%mod;
}
}
}if(op==-1){
int inv=power(n,mod-2);
for(int i=0;i<n;++i) a[i]=a[i]*inv%mod;
}
}