M_sea

洛谷4841 城市规划
Luogu分析设 $f(n)$ 为 $n$ 个节点的无向连通图个数, $g(n)$ 为 $n$ 个节点的无向图个数...
扫描右侧二维码阅读全文
20
2019/05

洛谷4841 城市规划

Luogu

分析

设 $f(n)$ 为 $n$ 个节点的无向连通图个数, $g(n)$ 为 $n$ 个节点的无向图个数。

那么显然有 $\large g(n)=2^{C_n^2}$ 。

枚举 $1$ 所在连通块的点数,可以得到 $\large g(n)=\sum\limits_{i=1}^nC_{n-1}^{i-1}f(i)g(n-i)$ 。

把组合数拆掉,然后两边除以一个 $(n-1)!$ 得到 $\large \frac{g(n)}{(n-1)!}=\sum\limits_{i=1}^n\frac{f(i)}{(i-1)!}\frac{g(n-i)}{(n-i)!}$ 。

这很像 $\mathrm{EGF}$ 的形式。那么构造生成函数 $\large F(x)=\sum\limits_{i=1}^{\infty}\frac{f(i)}{(i-1)!}x^i$,$\large G(x)=\sum\limits_{i=0}^{\infty}\frac{g(i)}{i!}x^i$ , $\large H(x)=\sum\limits_{i=1}^{\infty}\frac{g(i)}{(i-1)!}x^i$ 。

那么根据生成函数的性质有 $H(x)=F(x)G(x)$ ,也就是 $F(x)=H(x)G^{-1}(x)$ 。

直接多项式求逆即可。

代码

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') c=getchar();
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=320000+10;
const int mod=1004535809;

inline int qpow(int a,int b) {
    int c=1;
    for (;b;b>>=1,a=1ll*a*a%mod)
        if (b&1) c=1ll*c*a%mod;
    return c;
}

int r[N];

inline void NTT(int* A,int n,int op) {
    int lim=1,l=0; for (;lim<n;lim<<=1,++l);
    for (re int i=0;i<lim;++i) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
    for (re int i=0;i<lim;++i) if (i<r[i]) swap(A[i],A[r[i]]);
    for (re int i=1;i<lim;i<<=1) {
        int rot=qpow(op==1?3:(mod+1)/3,(mod-1)/(i<<1));
        for (re int j=0;j<lim;j+=(i<<1)) {
            int w=1;
            for (re int k=0;k<i;++k,w=1ll*w*rot%mod) {
                int x=A[j+k],y=1ll*w*A[j+k+i]%mod;
                A[j+k]=(x+y)%mod,A[j+k+i]=(x-y+mod)%mod;
            }
        }
    }
    if (op==-1) {
        int inv=qpow(lim,mod-2);
        for (re int i=0;i<lim;++i) A[i]=1ll*A[i]*inv%mod;
    }
}

inline void getInv(int* A,int* B,int n) {
    static int F[N],G[N];
    if (n==1) { B[0]=qpow(A[0],mod-2); return; }
    getInv(A,B,n>>1);
    for (re int i=0;i<n;++i) F[i]=A[i],G[i]=B[i];

    NTT(F,n<<1,1),NTT(G,n<<1,1);
    for (re int i=0;i<(n<<1);++i) F[i]=1ll*F[i]*G[i]%mod*G[i]%mod;
    NTT(F,n<<1,-1);
    for (re int i=0;i<n;++i) B[i]=((B[i]+B[i])%mod-F[i]+mod)%mod;
    for (re int i=0;i<(n<<1);++i) F[i]=G[i]=0;
}

int fac[N],inv[N],g[N];
int F[N],G[N],H[N],P[N];

int main() {
    int n=read();
    
    fac[0]=1;
    for (re int i=1;i<=n;++i) fac[i]=1ll*fac[i-1]*i%mod;
    inv[n]=qpow(fac[n],mod-2);
    for (re int i=n;i;--i) inv[i-1]=1ll*inv[i]*i%mod;

    g[0]=g[1]=1;
    for (re int i=2;i<=n;++i) g[i]=qpow(2,1ll*i*(i-1)/2%(mod-1));
    
    for (re int i=0;i<=n;++i) G[i]=1ll*g[i]*inv[i]%mod;
    for (re int i=1;i<=n;++i) H[i]=1ll*g[i]*inv[i-1]%mod;

    int lim=1; for (;lim<=n;lim<<=1);
    getInv(G,P,lim);
    NTT(P,lim,1),NTT(H,lim,1);
    for (re int i=0;i<lim;++i) F[i]=1ll*P[i]*H[i]%mod;
    NTT(F,lim,-1);
    printf("%d\n",1ll*F[n]*fac[n-1]%mod);
    return 0;
}
最后修改:2019 年 05 月 26 日 10 : 09 PM

发表评论