题意：

求n个点的无相连通图的个数。有编号

 

思路一：

至于为什么除以k!：（没有博客中说的那么简单）

实际上，

对于一个n的用k个自然数的拆分，每一个拆分的贡献是：

$\frac{n!*\Pi contribution}{\Pi cnt[i]!*\Pi i!}$这里i是所有出现过的自然数，cnt表示出现次数

因为认为集合两两之间都是不同的，但是对于相同的i，会计算多次。要除以出现次数的阶乘。对于不同的i，本身sz就不同，所以不会重复

然后考虑每个自然数拆分的方案数：

$f^k$

但是每个自然数拆分，会被计算：$\frac{k!}{\Pi cnt[i]}$次，再除掉

所以，实际上，贡献就是：$\frac{n!*\Pi contribution}{k!*\Pi i!}$

就是$\frac{f^k}{k!}$的第n项再乘上$n!$

 

然后就可以用麦克劳林展开，推出e^f的式子了

 

思路二：

考虑dp

f[i]，i个点的ans

无向图很好算.2^(C(n,2))

考虑在所有无向图中减去不连通的

不连通意味着某个点不能到达所有其他点

 

不妨从1来观察

枚举和1的联通块大小j

设g(n,j)，表示n个点，和1联通块大小为j的无向连通图个数

g(n,j)=C(n-1,j-1)*2^(C(n-j,2))*f[j]

 

f[n]=2^(C(n,2)-∑g(n,j) (1<=j<=n-1)

把g和f的关系带进去

然后移项过去，发现可以把j范围变成(1<=j<=n)就消掉了f[n]项

组合数展开，可以NTT

然后再转化成逆元

 

注意，这个逆元是在mod x^(n+1)下的

最后乘出来的长度是2*n的

注意长度

#include
     
      #define il inline#define reg register int#define int long long#define numb (ch^'0')using namespace std;typedef long long ll;il void rd(int &x){    char ch;bool fl=false;    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);    (fl==true)&&(x=-x);}namespace Miracle{const int N=8*130000+5;const int mod=1004535809;const int G=3;ll GI;int n;ll jie[N],ivv[N];ll f[N],ni[N],p[N],g[N],t[N],d[N],e[N];int rev[N];int qm(int x,int y){    int ret=1;    while(y){        if(y&1) ret=(ll)ret*x%mod;        x=(ll)x*x%mod;        y>>=1;    }    return ret;}int mo(int x){    return x>=mod?x-mod:x;}void pre(int n){    for(reg i=0;i
      
       >1]>>1|((i&1)?n>>1:0);    }}void NTT(int *f,int n,int c){    for(reg i=0;i
       
        rev[i]){            f[i]^=f[rev[i]]^=f[i]^=f[rev[i]];        }    }    for(reg p=2;p<=n;p<<=1){        int gen;        if(c==1) gen=qm(G,(mod-1)/p);        else gen=qm(GI,(mod-1)/p);        for(reg l=0;l
        
         >1]>>1|((i&1)?n>>1:0);    }    NTT(f,n,1);NTT(g,n,1);    for(reg i=0;i
         
          >1);    for(reg i=0;i
          
           >1]>>1|((i&1)?(2*n)>>1:0); } NTT(d,2*n,1);NTT(e,2*n,1); for(reg i=0;i<2*n;++i){ g[i]=mo(mo(2*d[i])-(ll)e[i]*d[i]%mod*d[i]%mod+mod); } NTT(g,2*n,-1); ll iv=qm(2*n,mod-2); for(reg i=0;i<2*n;++i){ if(i
           
            =0;--i){ ivv[i]=ivv[i+1]*(i+1)%mod; } for(reg i=0;i