【2016NOI十连赛2-2】黑暗

快来打我* 2022-10-03 00:37 49阅读 0赞

## 【2016NOI十连赛2-2】黑暗 ##

题目大意：定义一个无向图的权值为连通块个数的\\(m\\)次方。求\\(n\\)个点的所有无向图的权值和。多次询问。

数据范围：\\(T\\leq 1000,n\\leq 30000,m\\leq 15\\)

我们使用用第二类斯特林数转换\\(n^m\\)。  
\\\[ n^m=\\sum\_\{i=0\}^m\\binom\{n\}\{i\}i!\\begin\{Bmatrix\}m\\\\i\\end\{Bmatrix\} \\\]  
我们观察这个式子，相当于在\\(n\\)个连通块中选一个大小为\\(i\\)的子集，其贡献为\\(i!\\begin\{Bmatrix\}m\\\\i\\end\{Bmatrix\}\\)

我们设\\(f\_n\\)表示\\(n\\)个点的无向连通图的数量，\\(g\_\{n,m\}\\)表示\\(n\\)个点，\\(m\\)个连通块的数量。则答案为：  
\\\[ \\sum\_\{j=1\}^mj!\\begin\{Bmatrix\}m\\\\j\\end\{Bmatrix\}\\sum\_\{i=j\}^ng\_\{i,j\}\\binom\{n\}\{i\}2^\{\\binom\{n-i\}\{2\}\} \\\]  
设\\(A(x)=\\sum \\frac\{2^\{\\binom\{i\}\{2\}\}\}\{i!\}x^i\\)，也就是无向图的\\(OGF\\)。设\\(F(x)=\\sum \\frac\{f\_i\}\{i!\}\\)。

因为：  
\\\[ A(x)=\\sum\_\{i\}\\frac\{F(x)^i\}\{i\}=\\exp(F(x))\\\\ \\\]  
所以：  
\\\[ \\Rightarrow F(x)=\\ln(A(x)) \\\]  
代码：

#include<bits/stdc++.h>
    #define ll long long 
    #define N 30005
    
    using namespace std;
    inline int Get() {
        int x=0,f=1;
        char ch=getchar();
        while(ch<'0'||ch>'9') {
            if(ch=='-') f=-1;
            ch=getchar();
        }
        while('0'<=ch&&ch<='9') {
            x=(x<<1)+(x<<3)+ch-'0';
            ch=getchar();
        }
        return x*f;
    }
    
    const ll mod=998244353;
    ll ksm(ll t,ll x) {
        ll ans=1;
        for(;x;x>>=1,t=t*t%mod)
            if(x&1) ans=ans*t%mod;
        return ans;
    }
    
    int n,m;
    void NTT(ll *a,int d,int flag) {
        static int rev[N<<2];
        static ll G=3;
        int n=1<<d;
        for(int i=0;i<n;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<d-1);
        for(int i=0;i<n;i++) if(i<rev[i]) swap(a[i],a[rev[i]]);
        for(int s=1;s<=d;s++) {
            int len=1<<s,mid=len>>1;
            ll w=flag==1?ksm(G,(mod-1)/len):ksm(G,mod-1-(mod-1)/len);
            for(int i=0;i<n;i+=len) {
                ll t=1;
                for(int j=0;j<mid;j++) {
                    ll u=a[i+j],v=a[i+j+mid]*t%mod;
                    a[i+j]=(u+v)%mod;
                    a[i+j+mid]=(u-v+mod)%mod;
                    t=t*w%mod;
                }
            }
        }
        if(flag==-1) {
            ll inv=ksm(n,mod-2);
            for(int i=0;i<n;i++) a[i]=a[i]*inv%mod;
        }
    }
    
    void Inv(ll *inv,int d,ll *a) {
        static ll A[N<<2];
        if(d==0) {
            inv[0]=ksm(a[0],mod-2);
            return ;
        }
        Inv(inv,d-1,a);
        for(int i=1<<d;i<1<<d+1;i++) A[i]=inv[i]=0;
        for(int i=0;i<1<<d;i++) A[i]=a[i];
        NTT(inv,d+1,1),NTT(A,d+1,1);
        for(int i=0;i<1<<d+1;i++) inv[i]=(2*inv[i]-A[i]*inv[i]%mod*inv[i]%mod+mod)%mod;
        NTT(inv,d+1,-1);
        for(int i=1<<d;i<1<<d+1;i++) inv[i]=0;
    }
    
    void Int(ll *f,int d) {
        int n=1<<d;
        for(int i=0;i<n-1;i++) f[i]=f[i+1]*(i+1)%mod;
        f[n-1]=0;
    }
    void Der(ll *f,int d) {
        int n=1<<d;
        for(int i=n-1;i>0;i--) f[i]=f[i-1]*ksm(i,mod-2)%mod;
        f[0]=0;
    }
    void Ln(ll *ln,int d,ll *a) {
        static ll inv[N<<2],f[N<<2];
        for(int i=0;i<1<<d+1;i++) inv[i]=f[i]=0;
        for(int i=0;i<1<<d;i++) f[i]=a[i];
        Inv(inv,d,a);
        Int(f,d);
        NTT(inv,d+1,1),NTT(f,d+1,1);
        for(int i=0;i<1<<d+1;i++) f[i]=f[i]*inv[i]%mod;
        NTT(f,d+1,-1);
        Der(f,d);
        for(int i=0;i<1<<d;i++) ln[i]=f[i];
    }
    ll fac[N],ifac[N];
    ll S[20][20];
    ll e[N];
    ll C(int n,int m) {return fac[n]*ifac[m]%mod*ifac[n-m]%mod;}
    void pre(int n,int m) {
        for(int i=0;i<=n;i++) e[i]=ksm(2,i*(i-1)/2);
        fac[0]=1;
        for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;
        ifac[n]=ksm(fac[n],mod-2);
        for(int i=n-1;i>=0;i--) ifac[i]=ifac[i+1]*(i+1)%mod;
        S[0][0]=1;
        for(int i=1;i<=m;i++)
            for(int j=1;j<=i;j++)
                S[i][j]=(S[i-1][j-1]+j*S[i-1][j])%mod;
                
    }
    
    ll f[N<<2],g[20][N<<2];
    ll F[20][N];
    
    void DP(int n,int m) {
        static ll tem[N<<2];
        static ll A[N<<2],B[N<<2];
        for(int i=0;i<=n;i++) {
            tem[i]=e[i]*ifac[i]%mod;
        }
        int d=ceil(log2(n+1));
        Ln(f,d,tem);
        
        for(int i=1;i<=n;i++) {
            f[i]=f[i]*fac[i]%mod*ifac[i-1]%mod;
        }
        NTT(f,d+1,1);
        g[0][0]=1;
        for(int j=1;j<=m;j++) {
            for(int i=0;i<=n;i++) g[j][i]=g[j-1][i]*ifac[i]%mod;
            NTT(g[j],d+1,1);
            for(int i=0;i<1<<d+1;i++) g[j][i]=g[j][i]*f[i]%mod;
            NTT(g[j],d+1,-1);
            for(int i=n+1;i<1<<d+1;i++) g[j][i]=0;
            for(int i=1;i<=n;i++) g[j][i]=g[j][i]*fac[i-1]%mod;
        }
        for(int i=0;i<=n;i++) B[i]=e[i]*ifac[i]%mod;
        NTT(B,d+1,1);
        for(int j=1;j<=m;j++) {
            for(int i=0;i<1<<d+1;i++) A[i]=0;
            for(int i=1;i<=n;i++) A[i]=g[j][i]*ifac[i]%mod;
            NTT(A,d+1,1);
            for(int i=0;i<1<<d+1;i++) A[i]=A[i]*B[i]%mod;
            NTT(A,d+1,-1);
            for(int i=1;i<=n;i++) F[j][i]=A[i]*fac[i]%mod;
        }
    }
    
    int main() {
        pre(30000,15);
        DP(30000,15);
        int T=Get();
        while(T--) {
            n=Get(),m=Get();
            ll ans=0;
            for(int j=1;j<=m;j++) {
                ll res=0;
                (ans+=F[j][n]*fac[j]%mod*S[m][j])%=mod;
            }
            cout<<ans<<"\n";
        }
        return 0;
    }

转载于:https://www.cnblogs.com/hchhch233/p/11032350.html