【题解】城市规划 生成函数 luoguP4841 —Qiuly

设简单无向图的 $\rm{EGF}$ 为 $F$ ，简单连通图的 $\rm{EGF}$ 为 $C$ 。

显然有 $F(x)=\sum\limits_{i=0}^{\infty}2^{i\choose2}\frac{x^i}{i!}$ 。

然而现在需要求的是 $G(n)$ ，直接求 $G(n)$ 不好求。不过简单无向图是由若干简单连通图拼接而成的带标号集合，那么就有 $F=e^G$ ，于是就有 $G=\ln F$ 。

然后多项式求 $\ln$ 即可。

ps ：由于带标号，所以最后答案需要乘上 $n!$ .

#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N=4e5+2;
const ll mod=1004535809;

template <typename _Tp> inline void IN(_Tp&x) {
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    if(flag) x=-x;
}

namespace Poly {
    int H[N],A[N],B[N],flip[N];
    inline int pow(int x,ll y) {
        int res=1;x%=mod;
        for(;y;y>>=1,x=1ll*x*x%mod) if(y&1) res=1ll*res*x%mod;
        return res;
    }
    inline void NTT(int*f,int limit,short inv) {
        for(int i=0;i<limit;++i) 
            if(i<flip[i]) swap(f[i],f[flip[i]]);
        for(int p=2;p<=limit;p<<=1) {
            int len=p>>1,tmp=pow(3,(mod-1)/p);
            for(int k=0;k<limit;k+=p) {
                int buf=1;
                for(int l=k;l<k+len;++l,buf=1ll*buf*tmp%mod) {
                    int t=1ll*f[l+len]*buf%mod;
                    f[l+len]=(f[l]-t+mod)%mod,f[l]=(f[l]+t)%mod;
                }
            }
        }
        if(inv==1) return;
        int sl=pow(limit,mod-2);reverse(f+1,f+limit);
        for(int i=0;i<limit;++i) f[i]=1ll*f[i]*sl%mod;
    }
    void Inv(int*F,int*G,int deg) {
        if(deg==1) {G[0]=pow(F[0],mod-2);return;}
        Inv(F,G,(deg+1)>>1);
        int cnt=0,len=1;
        while(len<(deg<<1)) len<<=1,++cnt;
        for(int i=0;i<len;++i) flip[i]=(flip[i>>1]>>1)|((i&1)<<(cnt-1));
        for(int i=0;i<deg;++i) H[i]=F[i];
        for(int i=deg;i<len;++i) H[i]=0;
        NTT(G,len,1),NTT(H,len,1);
        for(int i=0;i<len;++i)
            G[i]=1ll*(2ll-1ll*H[i]*G[i]%mod+mod)*G[i]%mod;
        NTT(G,len,-1);
        for(int i=deg;i<len;++i) G[i]=0;
    }
    void Derivative(int*A,int*B,int len) {
        for(int i=1;i<len;++i) B[i-1]=1ll*i*A[i]%mod;
        B[len-1]=0;
    }
    void Integral(int*A,int*B,int len) {
        for(int i=1;i<len;++i) B[i]=1ll*pow(i,mod-2)*A[i-1]%mod;
        B[0]=0;
    }
    void Ln(int*F,int*G,int deg) {
        int cnt=0,len=1;
        while(len<=deg) len<<=1,++cnt;
        for(int i=0;i<len;++i) flip[i]=(flip[i>>1]>>1)|((i&1)<<(cnt-1));
        Derivative(F,A,deg),Inv(F,B,deg);
        NTT(A,len,1),NTT(B,len,1);
        for(int i=0;i<len;++i) A[i]=1ll*A[i]*B[i]%mod;
        NTT(A,len,-1),Integral(A,G,deg);
    }
}using namespace Poly;

int n,C[N],G[N],fac[N],inv[N];
int main() {
    IN(n),fac[0]=1;
    int m;for(m=1;m<=n;m<<=1);
    for(int i=1;i<=m;++i) fac[i]=1ll*fac[i-1]*i%mod;
    for(int i=1;i<=m;++i) inv[i]=pow(fac[i],mod-2);
    for(int i=0;i<=m;++i) G[i]=(i<2)?1:1ll*pow(2,(ll)i*(i-1)/2)*inv[i]%mod;
    Ln(G,C,m),printf("%d\n",1ll*C[n]*fac[n]%mod);
    return 0;
}

不知道为什么之前的板子总是出现一些奇奇怪怪的玄学问题，导致换一个板子跑跑出来就是错的 qaq，真玄学啊结果每次都要重打。