题目概述

求 $n$ 个点简单无向连通图的个数。

解题报告

我感觉好像重新学了一遍指数型生成函数的样子……

普通型生成函数解决的是组合问题，而指数型生成函数解决的是排列问题，比如把 $n​$ 个不同的物品划分成若干个不同的集合，我们可以令 $f_i​$ 表示划分出的集合大小为 $i​$ 的方案数，定义指数型生成函数 $\hat F(x)=\sum_{i=0}^{+\infty}f_i{x^i\over i!}​$ 。

那么 $\hat G(x)=\hat F(x)\cdot\hat F(x)$ 就是：

$$ g_i=i!\sum_{j=0}^{i}{f_j\over j!}{f_{i-j}\over(i-j)!}=\sum_{j=0}^{i}{i\choose j}f_jf_{i-j} $$

会发现 $i\choose j$ 的含义就是把大小为 $j$ 的集合和大小为 $i-j$ 的集合进行穿插的方案数（进行了排列），为了能够使用FFT加速卷积，我们可以把 $i!​$ 弄到左边去：

$$ {g_i\over i!}=\sum_{j=0}^{i}{f_j\over j!}{f_{i-j}\over (i-j)!} $$

也就是说指数型生成函数的卷积可以变成普通型生成函数的卷积，只需要在最后变回去就行了。

这样的话生成函数 $\sum_{i=0}^{+\infty}\hat F^i(x)$ 中 $x^n\over n!​$ 的系数就是上述问题的答案。

根据泰勒展开，我们可以得出：$e^x=\sum_{i=0}^{+\infty}{x^i\over i!}$ ，因此可以定义 $e^{F(x)}$ ：

$$ e^{F(x)}=\sum_{i=0}^{+\infty}{F^i(x)\over i!} $$

所以实际上 $e^{\hat F(x)}=\sum_{i=0}^{+\infty}{\hat F^i(x)\over i!}$ 就是 $n$ 个不同的物品划分成若干个相同的集合的生成函数。

然后我们来看这题，如果是简单无向图的个数，那么非常好求，他的指数型生成函数为：

$$ \hat G(x)=\sum_{i=0}^{+\infty}2^{{i\choose 2}}{x^i\over i!} $$

考虑到简单无向图是由若干个简单无向连通图构成的，假设简单无向连通图的指数型生成函数为 $\hat F(x)$ ，那么：

$$ \hat G(x)=\sum_{i=0}^{+\infty}{\hat F^i(x)\over i!}=e^{\hat F(x)} $$

因为虽然点是不同的，但是分成的部分是无区别的，所以要除以 $i!$ ，发现这就是上面说的模型！所以：

$$ \hat F(x)=ln\hat G(x) $$

因为是指数型生成函数，处理起来比较奇怪，我们先将其变成普通型生成函数。

令 $F(x)=\sum_{i=0}^{+\infty}{\hat F(x)_i\over i!}x^i,G(x)=\sum_{i=0}^{+\infty}{\hat G(x)_i\over i!}x^i$ ，根据之前加粗的那一句话，得到：

$$ F(x)=lnG(x) $$

直接多项式ln就行了，最后通过 $F(x)$ 求出 $\hat F(x)$ 。

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=262144,MOD=1004535809;

int n,G[maxn+5],F[maxn+5],tem[maxn+5],INV[maxn+5],fac[maxn+5],pre[maxn+5],rev[maxn+5],pw[2][maxn+5];

inline void Make(int n){
    pre[0]=INV[1]=1;for (int i=2;i<=n;i++) INV[i]=(LL)(MOD-MOD/i)*INV[MOD%i]%MOD;
    fac[0]=1;for (int i=1;i<=n;i++) fac[i]=(LL)fac[i-1]*i%MOD,pre[i]=(LL)pre[i-1]*INV[i]%MOD;
}
inline int Pow(int w,LL b) {int s;for (s=1;b;b>>=1,w=(LL)w*w%MOD) if (b&1) s=(LL)s*w%MOD;return s;}
inline void Pre(int n){
    for (int i=1;i<n;i++) rev[i]=(rev[i>>1]>>1)|((i&1)*(n>>1));
    for (int i=2;i<=n;i<<=1) pw[0][i]=Pow(3,(MOD-1)/i),pw[1][i]=Pow(pw[0][i],MOD-2);
}
inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
inline void NTT(int *a,int n,int f){
    for (int i=0;i<n;i++) if (i<rev[i]) swap(a[i],a[rev[i]]);
    for (int k=1;k<n;k<<=1){
        int gn=pw[f<0][k<<1],g=1,x,y;
        for (int i=0;i<n;i+=k<<1,g=1)
            for (int j=0;j<k;j++,g=(LL)g*gn%MOD)
                x=a[i+j],y=(LL)a[i+j+k]*g%MOD,AMOD(a[i+j]=x,y),AMOD(a[i+j+k]=x,MOD-y);
    }if (f<0) for (int i=0,INV=Pow(n,MOD-2);i<n;i++) a[i]=(LL)a[i]*INV%MOD;
}
void Inv(int *a,int *b,int n){
    if (n==1) {b[0]=Pow(a[0],MOD-2);return;}Inv(a,b,n>>1);Pre(n<<1);
    for (int i=0;i<n;i++) tem[i]=a[i],tem[i+n]=b[i+n]=0;NTT(tem,n<<1,1);NTT(b,n<<1,1);
    for (int i=0;i<(n<<1);i++) tem[i]=(LL)b[i]*(2+MOD-(LL)tem[i]*b[i]%MOD)%MOD;
    NTT(tem,n<<1,-1);for (int i=0;i<n;i++) b[i]=tem[i],b[i+n]=0;
}
inline void Ln(int *a,int *b,int n){
    static int A[maxn+5],B[maxn+5];for (int i=0;i<n;i++) A[i]=(LL)(i+1)*a[i+1]%MOD,A[i+n]=0;Inv(a,B,n);
    Pre(n<<1);NTT(A,n<<1,1);NTT(B,n<<1,1);for (int i=0;i<(n<<1);i++) B[i]=(LL)B[i]*A[i]%MOD;
    NTT(B,n<<1,-1);for (int i=1;i<n;i++) b[i]=(LL)INV[i]*B[i-1]%MOD;
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d",&n);int t;for (t=1;t<=n;t<<=1);Make(t);
    for (int i=0;i<=n;i++) G[i]=(LL)Pow(2,(LL)i*(i-1)>>1)*pre[i]%MOD;
    Ln(G,F,t);for (int i=0;i<=n;i++) F[i]=(LL)F[i]*fac[i]%MOD;printf("%d\n",F[n]);return 0;
}