[EOJ #643] 板题I

EOJ #643.

思路

设联通块的大小为$T$,则根据题意可知,答案为

$$\begin{split}
\sum\limits_ {\text{all graph}} T^m
&=\sum \limits_ {\text{all graph}} \sum \limits_ {i=1}^m{m\brace i} {T\choose i}\\
&=\sum \limits_ {i=1}^m\left({m\brace i}i!\cdot \sum \limits_ {\text{all graph}}{T\choose i}\right)
\end{split}$$

那么当前的问题就转化为了对于所有的$1\leq i\leq m$,求出$\sum \limits_ {\text{all graph}}{T\choose i}$

设$f_{i, j}$表示$j$个点构成的有$i$个联通块的有标号无向图个数,考虑枚举从$T$个联通块中选出的$i$个联通块的大小,则可得$$\sum \limits_ {\text{all graph}}{T\choose i}=\sum \limits_ {j=1}^{n}f_ {i, j}\cdot 2^{n-j\choose 2}\cdot {n\choose j}$$

让我们思考一下如何求$f$,$f_{1, i}$其实就是 [bzoj 3456] 城市规划 而对于剩下的$f$,枚举和$1$相连的联通块大小,有一个很显然的递推式$$f_{i, n}=\sum \limits_{j=1}^{n}{n-1\choose j-1}\cdot f_{1, i}\cdot f_{t-1, i}$$

代码

#include <iostream>
#include <cstdio>

template <typename T> void in(T &_){
    char c=getchar(); _=0; int fl=1;
    while(c<'0'||c>'9') fl=c=='-'?-1:fl, c=getchar();
    while(c>='0'&&c<='9') _=_*10+c-'0', c=getchar(); _*=fl;
}

const int MOD=998244353, G=3, iG=332748118, inv2=499122177, MX=65545;

int ksm(int x, int y){
    int z=1;
    for(; y; y>>=1, x=1LL*x*x%MOD) if(y&1) z=1LL*x*z%MOD;
    return z;
}

namespace Poly{
    int rev[MX], A[MX];
    
    void get_rev(int l){
        for(int i=0; i<l; i++) 
            rev[i]=(rev[i>>1]>>1) | ((i&1) ? (l>>1) : 0);
    }
    
    void ntt(int *P, int l, int opt){
        for(int i=0; i<l; i++) if(rev[i]>i)
            std::swap(P[i], P[rev[i]]);
        for(int i=1; i<l; i<<=1){
            int W=opt>0 ? G : iG;
            W=ksm(W, (MOD-1)/(2*i));
            for(int p=i*2, j=0; j<l; j+=p)
                for(int w=1, k=0; k<i; k++, w=1LL*w*W%MOD){
                    int X=P[j+k], Y=1LL*P[i+j+k]*w%MOD;
                    P[j+k]=(X+Y)%MOD; P[i+j+k]=(X-Y)%MOD;
                }
        }
        if(opt>0) return; int inv=ksm(l, MOD-2);
        for(int i=0; i<l; i++) P[i]=1LL*P[i]*inv%MOD;
    }
    
    void Inv(int *a, int *b, int n){
        if(n==1){b[0]=ksm(a[0], MOD-2); return;}
        Inv(a, b, (n+1)/2);
        int l=1; while(l<2*n) l<<=1; get_rev(l);
        for(int i=0; i<n; i++) A[i]=a[i];
        for(int i=n; i<l; i++) A[i]=0;
        ntt(b, l, 1); ntt(A, l, 1);
        for(int i=0; i<l; i++) b[i]=(2LL-1LL*A[i]*b[i]%MOD)%MOD*b[i]%MOD;
        ntt(b, l, -1);
        for(int i=n; i<l; i++) b[i]=0;
    }
}

int N, M, fac[MX], ifac[MX], inv[MX], f[16][MX], A[MX], B[MX], s[16][16];

void pre(){
    inv[1]=fac[0]=ifac[0]=s[0][0]=1;
    for(int i=2; i<=N; i++) inv[i]=1LL*(MOD-MOD/i)*inv[MOD%i]%MOD;
    for(int i=1; i<=N; i++) fac[i]=1LL*i*fac[i-1]%MOD;
    for(int i=1; i<=N; i++) ifac[i]=1LL*inv[i]*ifac[i-1]%MOD;
    for(int i=1; i<=M; i++) for(int j=1; j<=i; j++) 
        s[i][j]=(1LL*j*s[i-1][j]%MOD+s[i-1][j-1])%MOD;
}

void get_g1(){
    for(int i=0; i<=N; i++) A[i]=1LL*ifac[i]*ksm(2, i*(i-1)/2)%MOD;
    Poly::Inv(A, f[1], N+1);
    for(int i=1; i<=N; i++) A[i]=1LL*ifac[i-1]*ksm(2, i*(i-1)/2)%MOD;
    A[0]=0;
    int l=1; while(l<=2*N) l<<=1; Poly::get_rev(l);
    Poly::ntt(A, l, 1); Poly::ntt(f[1], l, 1);
    for(int i=0; i<l; i++) f[1][i]=1LL*f[1][i]*A[i]%MOD;
    Poly::ntt(f[1], l, -1);
    for(int i=N+1; i<l; i++) f[1][i]=0; f[1][0]=0;
    for(int i=1; i<=N; i++) f[1][i]=1LL*f[1][i]*fac[i-1]%MOD;
}

void get_g(){
    int l=1; while(l<=2*N) l<<=1; Poly::get_rev(l);
    for(int t=2; t<=M; t++){
        for(int i=1; i<=N; i++) A[i]=1LL*f[1][i]*ifac[i-1]%MOD;
        for(int i=N+1; i<l; i++) A[i]=0; A[0]=0;
        for(int i=1; i<=N; i++) f[t][i]=1LL*f[t-1][i]*ifac[i]%MOD;
        Poly::ntt(A, l, 1); Poly::ntt(f[t], l, 1);
        for(int i=0; i<l; i++) f[t][i]=1LL*f[t][i]*A[i]%MOD;
        Poly::ntt(f[t], l, -1);
        for(int i=N+1; i<l; i++) f[t][i]=0; f[t][0]=0;
        for(int i=1; i<=N; i++) f[t][i]=1LL*f[t][i]*fac[i-1]%MOD;
    }
}

int C(int x, int y){return 1LL*fac[x]*ifac[y]%MOD*ifac[x-y]%MOD;}

int main(){
    in(N); in(M);
    pre(); get_g1(); get_g();
    int ans=0;
    for(int i=1; i<=M; i++){
        int tmp=0;
        for(int j=1; j<=N; j++) 
            tmp=(tmp+1LL*f[i][j]*ksm(2, (N-j)*(N-j-1)/2)%MOD*C(N, j)%MOD)%MOD;
        ans=(ans+1LL*tmp*fac[i]%MOD*s[M][i]%MOD)%MOD;
    }
    printf("%d\n", (ans+MOD)%MOD);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注