题目描述

刚刚解决完电力网络的问题, 阿狸又被领导的任务给难住了.

刚才说过, 阿狸的国家有n个城市, 现在国家需要在某些城市对之间建立一些贸易路线, 使得整个国家的任意两个城市都直接或间接的连通.

为了省钱, 每两个城市之间最多只能有一条直接的贸易路径. 对于两个建立路线的方案, 如果存在一个城市对, 在两个方案中是否建立路线不一样, 那么这两个方案就是不同的, 否则就是相同的. 现在你需要求出一共有多少不同的方案.

好了, 这就是困扰阿狸的问题. 换句话说, 你需要求出n个点的简单(无重边无自环)无向连通图数目.

由于这个数字可能非常大, 你只需要输出方案数mod 1004535809(479 * 2 ^ 21 + 1)即可.

题解

其实就是无向连通图计数问题。

都给了这个模数了，肯定要FFT做。

考虑定义生成函数F表示n个点的连通图个数。

G表示n个点的无向图个数，各一发现，G[i]=2^C(n,2)。

然后考虑dp出G来。

G[n]=∑F[i]*G[n-i]*C(n-1,i-1)

这里的i枚举的是和1点连通的点的个数。

然后看到组合数就得想一想怎么把它拆开。

G[n]=∑F[i]*G[n-i]*(n-1)!*(1/(i-1)!)*(1/(n-i)!)

把右边的(n-1)!移到左边去。

G[n]/(n-1)!=∑F[i]/(i-1)!*G[n-i]/(n-i)!

于是这个式子变成可卷积的形式。

那么我们令

C=F[i]/(i-1)!  

Q=2^C(n,2)/n!

Q'=2^C(n,2)/(n-1)!

那么Q'=Q*C

C=Q*Q'^-1

求一个逆就好了。

注意：当我们预处理多项式的时候，遇到一些奇怪的式子的时候，要想一想它的实际意义。

例如G[0]表示0个点的答案显然为1，G[1]同理也是1，但按照式子算的话为0，这时应从实际的角度计算。

C[0]中有一项为(-1)!但是并没有找到什么和实际有关的，所以我们认为这一项为0。

代码

#include
     
      #include
      
       #define N 550002using namespace std;typedef long long ll;ll g[N],a[N],b[N],rev[N],c[N],n,jie[N],ni[N],yu[N];const ll mod=1004535809;const ll G=3;const ll Gi=334845270;inline int rd(){    int x=0;char c=getchar();bool f=0;    while(!isdigit(c)){
   if(c=='-')f=1;c=getchar();}    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}    return f?-x:x; }inline ll power(ll x,ll y){    ll ans=1;    while(y){
   if(y&1)ans=ans*x%mod;x=x*x%mod;y>>=1;}    return ans;} inline void NTT(ll *a,int l,int tag){    for(int i=1;i
       
        rev[i])swap(a[i],a[rev[i]]);    for(int i=1;i
        
         <<=1){        ll wn=power(tag==1?G:Gi,(mod-1)/(i<<1));        for(int j=0;j
         
          <<1)){            ll w=1;            for(int k=0;k
          
           >1); int l=1,L=0; while(l<=(n<<1))l<<=1,L++; for(int i=1;i
           
            >1]>>1)|((i&1)<<(L-1)); for(int i=0;i
            
             =0;--i)ni[i]=ni[i+1]*(i+1)%mod; yu[0]=yu[1]=1; for(int i=2;i<=n;++i)yu[i]=power(2,C(i)); g[0]=yu[0]*ni[0]%mod; for(int i=1;i<=n;++i){ c[i]=yu[i]*ni[i-1]%mod; g[i]=yu[i]*ni[i]%mod; }// for(int i=0;i<=n;++i)cout<
             
              <<" ";puts("");// for(int i=0;i<=n;++i)cout<
              
               <<" ";puts(""); inv(n+1); int l=1,L=0; while(l<=(n<<1))l<<=1,L++; for(int i=1;i
               
                >1]>>1)|((i&1)<<(L-1));// for(int i=0;i
                
                 <
                 
                  <<" ";cout<