题意：n个点组成的无向连通图个数

---

以前做过，今天复习一下

令\(f[n]\)为n个点的无向连通图个数

n个点的完全图个数为\(2^{\binom{n}{2}}\)

和Bell数的推导很类似，枚举第一个cc的点的个数

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

整理后

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

这是卷积的形式

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

多项式求逆就可做了

注意\(b_0=1\)

其实就是EGP求ln......

简单的有标号集合计数

\[ G(x) = \sum_{i\ge 0} 2^{\binom{i}{2}}\frac{x^i}{i!} = \sum_{i \ge 0} \frac{F(x)^i}{i!} = e^{F(x)}\\ F(x) = \ln G(x) = \int \frac{G'(x)}{G(x)}dx \]

第一份是多项式求ln的代码，注意EGP要除以阶乘逆元

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;typedef long long ll;const int N = (1<<18) + 5;inline int read(){    char c=getchar();int x=0,f=1;    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}    return x*f;}int P = 1004535809, inv2 = (P+1)/2;inline int Pow(ll a, int b) {    ll ans = 1;    for(; b; b>>=1, a=a*a%P)        if(b&1) ans=ans*a%P;    return ans;}ll inv[N];namespace ntt {    int g = 3, rev[N];    void dft(int *a, int n, int flag) {        int k = 0; while((1<
         
          < n) k++; for(int i=0; i
          
           >1]>>1) | ((i&1)<<(k-1)); if(i < rev[i]) swap(a[i], a[rev[i]]); } for(int l=2; l<=n; l<<=1) { int m = l>>1, wn = Pow(g, flag == 1 ? (P-1)/l : P-1-(P-1)/l); for(int *p = a; p != a+n; p += l) for(int k=0, w=1; k
           
            >1); int n = l<<1; for(int i=0; i
            
             0; i--) b[i] = (ll) inv[i] * b[i-1] %P; b[0] = 0; for(int i=l; i
            
           
          
         
        
       
      
     
    

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;typedef long long ll;const int N = (1<<18) + 5;inline int read(){    char c=getchar();int x=0,f=1;    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}    return x*f;}ll P = 1004535809;inline ll Pow(ll a, int b) {    ll ans = 1;    for(; b; b>>=1, a=a*a%P)        if(b&1) ans=ans*a%P;    return ans;}inline void mod(int &x) {if(x>=P) x-=P; else if(x<0) x+=P;}namespace fnt {    int n, g=3, rev[N];    void dft(int *a, int n, int flag=1) {        for(int i=0; i
         
          >1; ll wn = Pow(g, flag==1 ? (P-1)/l : P-1-(P-1)/l); for(int *p=a; p!=a+n; p+=l) { ll w = 1; for(int k=0; k
          
           >1); int n = 1, k = 0; while(n < l<<1) n<<=1, k++; for(int i=0; i
           
            >1]>>1) | ((i&1)<<(k-1)); for(int i=0; i