传送门

题意简述：求\(n​\)个点的简单无向连通图的数量\(\mod \;1004535809​\)，\(n \leq 130000​\)

经典好题呀！这里介绍两种做法：多项式求逆、多项式求对数

先是多项式求逆的做法。

我们发现直接求连通图的数量并不好求，所以我们用所有图的数量\(g_n​\)减去不连通的数量，得到连通图的个数\(f_n​\)。

易得\(g_n=2^{n \choose 2}​\)

考虑DP，枚举1号点所在的连通块大小，有\(f_n=g_n-\sum_{i=1}^{n-1} { {n-1} \choose {i-1} } f_i g_{n-i}\)

这个式子不怎么好看，移项一下变成\(g_n=\sum_{i=1}^n { {n-1} \choose {i-1} } f_i g_{n-i}\)

再化一下，\(\frac{g_n}{(n-1)!}=\sum_{i=1}^n \frac{f_i}{(i-1)!}\frac{g_{n-i}}{(n-i)!}\)

注意到右边很像一个卷积，我们记这样一些生成函数：

所以\(A=C*B^{-1}​\)

\(B,C​\)均可以\(O(n)​\)求出，那么写一个多项式求逆就做完了。

接下来是多项式求对数。

仍然设\(f_n\)为\(n\)个点的无向连通图的个数，\(g_n\)为\(n\)个点的无向图的数量。

仍然有\(g_n=2^{n\choose 2}\)。

写出\(f,g​\)的指数生成函数：

注意到一个无向图由许多个连通块组成。我们可以枚举组成的数量，得到

为什么要除以\(n!\)呢？因为这些连通块是不分顺序的，所以要除以\(n!\)。

你再观察一下右边，发现这是个麦克劳林级数：

所以有

把板子粘上来即可。

代码（只有多项式求逆的，求对数的懒得写）（之前写的，和上面的定义略有不同）：

#include<bits/stdc++.h>

namespace my_std{

    using namespace std;

    #define pii pair<int,int>

    #define fir first

    #define sec second

    #define MP make_pair

    #define rep(i,x,y) for (int i=(x);i<=(y);i++)

    #define drep(i,x,y) for (int i=(x);i>=(y);i--)

    #define go(x) for (int i=head[x];i;i=edge[i].nxt)

    #define sz 606060

    #define mod 1004535809

    typedef long long ll;

    template<typename T>

    inline void read(T& t)

    {

        t=0;char f=0,ch=getchar();

        double d=0.1;

        while(ch>'9'||ch<'0') f|=(ch=='-'),ch=getchar();

        while(ch<='9'&&ch>='0') t=t*10+ch-48,ch=getchar();

        if(ch=='.')

        {

            ch=getchar();

            while(ch<='9'&&ch>='0') t+=d*(ch^48),d*=0.1,ch=getchar();

        }

        t=(f?-t:t);

    }

    template<typename T,typename... Args>

    inline void read(T& t,Args&... args){read(t); read(args...);}

    void file()

    {

        #ifndef ONLINE_JUDGE

        freopen("a.txt","r",stdin);

        #endif

    }

//	inline ll mul(ll a,ll b){ll d=(ll)(a*(double)b/mod+0.5);ll ret=a*b-d*mod;if (ret<0) ret+=mod;return ret;}

}

using namespace my_std;

const ll g=3;

int limit,r[sz];

ll ksm(ll x,ll y)

{

    y%=(mod-1);

    ll ret=1;

    for (;y;y>>=1,x=x*x%mod) if (y&1) ret=ret*x%mod;

    return ret;

}

ll inv(ll x){return ksm(x,mod-2);}

void NTT_init(int n)

{

    limit=1;int l=-1;

    while (limit<=n+n) limit<<=1,l++;

    rep(i,0,limit-1) r[i]=(r[i>>1]>>1)|((i&1)<<l);

}

void NTT(ll *a,int type)

{

    rep(i,0,limit-1) if (i<r[i]) swap(a[i],a[r[i]]);

    for (int mid=1;mid<limit;mid<<=1)

    {

        ll Wn=ksm(g,(mod-1)/mid>>1);if (type==-1) Wn=inv(Wn);

        for (int len=mid<<1,j=0;j<limit;j+=len)

        {

            ll w=1;

            for (int k=0;k<mid;k++,w=w*Wn%mod)

            {

                ll x=a[j+k],y=w*a[j+k+mid]%mod;

                a[j+k]=(x+y)%mod;a[j+k+mid]=(x-y+mod)%mod;

            }

        }

    }

    if (type==1) return;

    ll I=inv(limit);

    rep(i,0,limit-1) (a[i]*=I)%=mod;

}

ll a[sz],c[sz];

ll F[sz],d[sz],e[sz];

void work_inv(int n)

{

    if (n==1) return (void)(F[0]=inv(c[0]));

    int mid;

    work_inv(mid=(n+1)>>1);

    NTT_init(n);

    rep(i,0,mid-1) d[i]=F[i];rep(i,mid,limit-1) d[i]=0;

    rep(i,0,n-1) e[i]=c[i];rep(i,n,limit-1) e[i]=0;

    NTT(d,1);NTT(e,1);

    rep(i,0,limit-1) d[i]=d[i]*(mod+2ll-d[i]*e[i]%mod)%mod;

    NTT(d,-1);

    rep(i,0,n-1) F[i]=d[i];

}

int n;

ll fac[sz];

int main()

{

    file();

    read(n);

    fac[0]=1;

    rep(i,1,n) fac[i]=fac[i-1]*i%mod;

    rep(i,0,n) a[i]=ksm(2,1ll*i*(i+1)/2)*inv(fac[i])%mod;

    rep(i,0,n) c[i]=ksm(2,1ll*i*(i-1)/2)*inv(fac[i])%mod;

    work_inv(n+1);

    NTT_init(n+1);

    NTT(a,1);NTT(F,1);

    rep(i,0,limit-1) F[i]=F[i]*a[i]%mod;

    NTT(F,-1);

    cout<<F[n-1]*fac[n-1]%mod;

}