嘤嘤嘤看不透生成函数怎么办啊
设$f(n)$为$n$个点的有标号无向连通图个数，$g(n)$为$n$个点的无向图个数。
显然$g(n)=2^{\frac{n(n-1)}{2}}$。
考虑容斥转移，用总的减去不合法的。
$f(0)=0,f(n)=g(n)-\sum\limits_{i=1}^{n-1}C_{n-1}^{i-1}f(i)g(n-i)$
啥意思呢？$g(n)$是总数，然后枚举$1$号点所在联通块的大小。$C_{n-1}^{i-1}$选出和$1$一个联通块的点，$f(i)$让它们联通，剩下$n-i$个点随便连$g(n-i)$。后面那一坨不是在容斥，它只是把所有不同类型的不合法情况枚举了一遍，所以不用乘容斥系数。
带组合数可以考虑$EGF$了，把组合数拆开：
$f(n)=g(n)-\sum\limits_{i=1}^{n-1}\dfrac{(n-1)!}{(i-1)!(n-i)!}f(i)g(n-i)$
$(n-1)!$除过去：
$\dfrac{f(n)}{(n-1)!}=\dfrac{g(n)}{(n-1)!}-\sum\limits_{i=1}^{n-1}\dfrac{f(i)}{(i-1)!}\dfrac{g(n-i)}{(n-i)!}$
这个式子涉及到三种形式：$\dfrac{f(n)}{(n-1)!},\dfrac{g(n)}{(n-1)!},\dfrac{g(n)}{n!}$
令$\{f(n-1)\}$的$EGF$为$F(x)=\sum\limits_{n=1}^\infty \dfrac{f(n)}{(n-1)!}x^n$，$\{g(n-1)\}$的$EGF$为$G(x)=\sum\limits_{n=1}^\infty \dfrac{g(n)}{(n-1)!}x^n$，$\{g(n)\}$的$EGF$为$G’(x)=\sum\limits_{n=0}^\infty \dfrac{g(n)}{n!}x^n$。
$F=\sum\limits_{n=1}^\infty x^n\left(\dfrac{g(n)}{(n-1)!}-\sum\limits_{i=1}^{n-1}\dfrac{f(i)}{(i-1)!}\dfrac{g(n-i)}{(n-i)!}\right)$
后面那一坨像卷积，但上界不对劲。单独处理一下$i=n$的情况，顺便把$G$提出来：
$F=G-\sum\limits_{n=0}^\infty x^n\left(\sum\limits_{i=1}^{n}\dfrac{f(i)}{(i-1)!}\dfrac{g(n-i)}{(n-i)!}-\dfrac{f(n)}{(n-1)!}\right)$
$F=G-F\times G’+F$
$F=G\times G’^{-1}$
多项式求逆+乘法，最后答案要乘个$(n-1)!$。
或者也可以不用容斥推，按$1$号点所在联通块大小把$g(n)$分类：
$g(n)=\sum\limits_{i=1}^nC_{n-1}^{i-1}f(i)g(n-i)$
结果是一样的。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define maxn 270005
#define inf 0x3f3f3f3f
const int mod = 1004535809;
const int g = 3;
using namespace std;
inline int read(){
int x=0,y=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return y?-x:x;
}
inline int quickpow(int x,int y=mod-2){
int ans=1;
while(y){
if(y&1)ans=1ll*ans*x%mod;
x=1ll*x*x%mod,y>>=1;
}
return ans;
}
const int ig = quickpow(g);
int tr[maxn];
inline int qm(int x){return x>=mod?x-mod:x;}
void NTT(int *f,int n,bool t){
for(register int i=0;i<n;++i)if(i<tr[i])swap(f[i],f[tr[i]]);
for(register int p=2;p<=n;p<<=1){
int len=p>>1,o=quickpow(t?ig:g,(mod-1)/p);
for(register int i=0;i<n;i+=p){
int gen=1,cop;
for(register int j=i;j<i+len;++j){
cop=1ll*f[j+len]*gen%mod,gen=1ll*gen*o%mod;
f[j+len]=qm(f[j]+mod-cop),f[j]=qm(f[j]+cop);
}
}
}
if(t){
int inv=quickpow(n);
for(register int i=0;i<n;++i)f[i]=1ll*f[i]*inv%mod;
}
}
int A[maxn],B[maxn];
void mul(int *a,int *b,int *c,int n,int lim){
for(register int i=0;i<n;++i)A[i]=a[i],B[i]=b[i];
int m=n<<1;
n=1;
while(n<m)n<<=1;
for(register int i=0;i<n;++i)tr[i]=(tr[i>>1]>>1)|(i&1?n>>1:0);
NTT(A,n,0),NTT(B,n,0);
for(register int i=0;i<n;++i)A[i]=1ll*A[i]*B[i]%mod;
NTT(A,n,1);
for(register int i=0;i<lim;++i)c[i]=A[i];
for(register int i=0;i<n;++i)A[i]=B[i]=0;
}
int invR[maxn],_invR[maxn];
void Inv(int *f,int *g,int n){
#define R invR
#define _R _invR
int lim=2;
R[0]=quickpow(f[0]);
while(lim<n<<1){
for(register int i=0;i<lim;++i)_R[i]=R[i],R[i]=f[i];
for(register int i=0;i<lim<<1;++i)tr[i]=(tr[i>>1]>>1)|(i&1?lim:0);
NTT(_R,lim<<1,0),NTT(R,lim<<1,0);
for(register int i=0;i<lim<<1;++i)R[i]=1ll*qm(2+mod-1ll*R[i]*_R[i]%mod)*_R[i]%mod;
NTT(R,lim<<1,1),lim<<=1;
for(register int i=lim>>1;i<lim;++i)R[i]=0;
}
for(register int i=0;i<n;++i)g[i]=R[i];
for(register int i=0;i<lim;++i)R[i]=_R[i]=0;
}
int fac[maxn]={1},inv[maxn],G[maxn],_G[maxn];
int main(){
int n=read();
for(register int i=1;i<=n;++i)fac[i]=1ll*fac[i-1]*i%mod;
inv[n]=quickpow(fac[n]);
for(register int i=n-1;~i;--i)inv[i]=1ll*inv[i+1]*(i+1)%mod;
for(register int i=1;i<=n;++i){
int k=quickpow(2,(1ll*i*(i-1)>>1)%(mod-1));
G[i]=1ll*k*inv[i-1]%mod;
_G[i]=1ll*k*inv[i]%mod;
}
_G[0]=1;
Inv(_G,_G,n+1),mul(_G,G,G,n+1,n+1);
printf("%d\n",1ll*G[n]*fac[n-1]%mod);
}
