题解
设 (f_n) 表示 (n) 个点的无向联通图个数，(g_n) 表示 (n) 个点的无向图个数，显然 (g_n=2^{ binom{n}{2}})。
那么可得
[g_n=sum_{i=1}^n binom{n-1}{i-1}f_ig_{n-i}
]
意思就是枚举 (1) 所在的最大联通块的大小，统计方案数。
将 (g_n=2^{ binom{n}{2}}) 带入原式，并进行化简
[2^{ binom{n}{2}}=sum_{i=1}^n binom{n-1}{i-1}f_i2^{ binom{n-i}{2}}\
2^{ binom{n}{2}}=sum_{i=1}^nfrac{(n-1)!}{(i-1)!(n-i)!}f_i2^{ binom{n-i}{2}}\
frac{2^{ binom{n}{2}}}{(n-1)!}=sum_{i=1}^nfrac{f_i2^{ binom{n-i}{2}}}{(i-1)!(n-i)!}
]
发现这是个卷积形式，设
[F(x)=sum_{i=1}^{+infty}frac{f_i}{(i-1)!}x^i\
G(x)=sum_{i=0}^{+infty}frac{2^{ binom{i}{2}}}{i!}x^i\
H(x)=sum_{i=1}^{+infty}frac{2^{ binom{i}{2}}}{(i-1)!}x^i
]
则
[H=F*G\
F=H*G^{-1}
]
先对 (G) 求逆，再与 (H) 卷积即可，复杂度 (mathcal{O m (nlogn)})。
Code
#include<bits/stdc++.h>
#define Re register
#define ri Re signed
#define pd(i) ++i
#define bq(i) --i
namespace IO{
char buf[1<<21],*p1=buf,*p2=buf;
#define gc() p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?(-1):*p1++
struct nanfeng_stream{
template<typename T>inline nanfeng_stream &operator>>(T &x) {
Re bool f=false;x=0;Re char ch=gc();
while(!isdigit(ch)) f|=ch=='-',ch=gc();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=gc();
return x=f?-x:x,*this;
}
}cin;
}
using IO::cin;
namespace nanfeng{
#define FI FILE *IN
#define FO FILE *OUT
template<typename T>inline T cmax(T x,T y) {return x>y?x:y;}
template<typename T>inline T cmin(T x,T y) {return x>y?y:x;}
using ll=long long;
static const int N=1<<19,MOD=1004535809;
ll h[N],g[N],f[N],gt[N],gc[N],frac[N],inv[N],w1[N],w2[N];
int R[N],n,len,st;
auto fpow=[](int x,int y) {
ll res=1;
while(y) {
if (y&1) res=res*x%MOD;
x=1ll*x*x%MOD;
y>>=1;
}
return res;
};
auto MD=[](ll x) {return x>=MOD?x-MOD:x;};
auto NTT1=[](ll *a) {
for (ri i(0);i<st;pd(i)) if (R[i]>i) std::swap(a[R[i]],a[i]);
for (ri t(st>>1),d(1);d<st;t>>=1,d<<=1)
for (ri i(0);i<st;i+=d<<1)
for (ri j(0);j<d;pd(j)) {
const ll tmp=w1[t*j]*a[i+j+d]%MOD;
a[i+j+d]=(a[i+j]-tmp+MOD)%MOD;
a[i+j]=MD(a[i+j]+tmp);
}
};
auto NTT2=[](ll *a) {
for (ri i(0);i<st;pd(i)) if (R[i]>i) std::swap(a[R[i]],a[i]);
for (ri t(st>>1),d(1);d<st;t>>=1,d<<=1)
for (ri i(0);i<st;i+=d<<1)
for (ri j(0);j<d;pd(j)) {
const ll tmp=w2[t*j]*a[i+j+d]%MOD;
a[i+j+d]=(a[i+j]-tmp+MOD)%MOD;
a[i+j]=MD(a[i+j]+tmp);
}
ll Inv=fpow(st,MOD-2);
for (ri i(0);i<st;pd(i)) a[i]=a[i]*Inv%MOD;
};
void calc(int deg) {
if (deg==1) return (void)(gt[0]=fpow(g[0],MOD-2));
calc(deg+1>>1);
len=0,st=1;
while(st<=deg<<1) st<<=1,++len;
for (ri i(0);i<st;pd(i)) R[i]=(R[i>>1]>>1)|((i&1)<<(len-1));
w1[1]=fpow(3,(MOD-1)/st),w2[1]=fpow(w1[1],MOD-2);
for (ri i(2);i<st;pd(i)) w1[i]=w1[i-1]*w1[1]%MOD,w2[i]=w2[i-1]*w2[1]%MOD;
memcpy(gc,g,sizeof(ll)*deg);
memset(gc+deg,0,sizeof(ll)*(st-deg));
NTT1(gt),NTT1(gc);
for (ri i(0);i<st;pd(i)) gt[i]=(2ll-gc[i]*gt[i]%MOD+MOD)%MOD*gt[i]%MOD;
NTT2(gt);
memset(gt+deg,0,sizeof(ll)*(st-deg));
}
inline int main() {
// FI=freopen("nanfeng.in","r",stdin);
// FO=freopen("nanfeng.out","w",stdout);
cin >> n;
++n;
frac[0]=inv[0]=1;
for (ri i(1);i<=n;pd(i)) frac[i]=frac[i-1]*i%MOD;
inv[n]=fpow(frac[n],MOD-2);
for (ri i(n-1);i;bq(i)) inv[i]=inv[i+1]*(i+1)%MOD;
g[0]=1;
for (ri i(1);i<=n;pd(i)) {
ll tmp=fpow(2,(1ll*i*(i-1)>>1)%(MOD-1));
h[i]=tmp*inv[i-1]%MOD,g[i]=tmp*inv[i]%MOD;
}
w1[0]=w2[0]=1;
calc(n);
st=1,len=0;
while(st<=n<<1) st<<=1,++len;
memset(gt+n,0,sizeof(ll)*(st-n+1));
for (ri i(0);i<st;pd(i)) R[i]=(R[i>>1]>>1)|((i&1)<<(len-1));
w1[1]=fpow(3,(MOD-1)/st),w2[1]=fpow(w1[1],MOD-2);
for (ri i(2);i<st;pd(i)) w1[i]=w1[i-1]*w1[1]%MOD,w2[i]=w2[i-1]*w2[1]%MOD;
NTT1(gt),NTT1(h);
for (ri i(0);i<st;pd(i)) h[i]=h[i]*gt[i]%MOD;
NTT2(h);
printf("%lld
",h[n-1]*frac[n-2]%MOD);
return 0;
}
}
int main() {return nanfeng::main();}