感觉这个题是真的神仙啊，思路是真的难想

首先设\(f(i)\)为\(i\)个点的无向连通图个数，然后设\(g(i)\)为\(i\)个点的图的个数（注意，此处不一定联通）

那么我们考虑枚举\(1\)号点所在的联通块的大小

显然有

\[ g(n)=\sum_{i=1}^nf(i)\binom{n-1}{i-1}g(n-i)\\ \]

考虑到

\[ g(n)=2^{\binom{n}{2}}\\ \]

所以有

\[ \sum_{i=1}^{n}f(i)\binom{n-1}{i-1}2^{\binom{n-i}{2}}=2^{\binom{n}{2}}\\ \]

后面的应该就很好推了，这个题主要的难点是考虑枚举\(1\)所在的联通块大小

后面还是套路，把组合数拆开

\[ \sum_{i=1}^nf(i)\frac{(n-1)!}{(n-i)!(i-1)!}2^{\binom{n-i}{2}}=2^{\binom{n}{2}}\\ \]

把相同项移到一起去

\[ \sum_{i=1}^n\frac{f(i)}{(i-1)!}\frac{2^{\binom{n-i}{2}}}{(n-i)!}=\frac{2^{\binom{n}{2}}}{(n-1)!}\\ \]

这个式子已经很眼熟了，再设

\[ A(x)=\sum_{i=0}\frac{f(i)}{(i-1)!}x^i\\ B(x)=\sum_{i=0}\frac{2^{\binom{i}{2}}}{i!}x^i\\ C(x)=\sum_{i=0}\frac{2^{\binom{i}{2}}}{(i-1)!}x^i\\ \]

很显然有

\[ C(x)=A(x)B(x)\\ A(x)=C(x)B(x)^{-1} \]

然后就可以多项式求逆+NTT了

代码：

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;void read(int &x){ char ch;bool ok; for(ok=0,ch=getchar();!isdigit(ch);ch=getchar())if(ch=='-')ok=1; for(x=0;isdigit(ch);x=x*10+ch-'0',ch=getchar());if(ok)x=-x;}#define rg registerconst int maxn=4e5+10,mod=1004535809,g=3,gi=334845270,modd=mod-1;int n,a[maxn],b[maxn],c[maxn],m,fac[maxn],inv[maxn],len,ans,r[maxn],mx;int mul(int x,int y){return 1ll*x*y-1ll*x*y/mod*mod;}int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}int del(int x,int y){return x-y<0?x-y+mod:x-y;}int mi(int a,int b){ int ans=1; while(b){ if(b&1)ans=mul(ans,a); b>>=1,a=mul(a,a); } return ans;}void ntt(int *a,int n,int f){ for(rg int i=0;i
          
           i)swap(a[i],a[r[i]]); for(rg int i=1;i
           
            <<=1){ int wn=mi(f?g:gi,(mod-1)/(i<<1)); for(rg int j=0;j
            
             <<1){ int w=1; for(rg int k=0;k
             
              >1); m=n;len=0; for(n=1;n<=m<<1;n<<=1)len++; for(rg int i=0;i
              
               >1]>>1)|((i&1)<<(len-1)); for(rg int i=0;i
               
                >1]>>1)|((i&1)<<(len-1)); ntt(b,n,1),ntt(c,n,1); for(rg int i=0;i