[BZOJ]5093: [Lydsy1711月賽]圖的價值 NTT+第二類斯特林數

Description

“簡單無向圖”是指無重邊、無自環的無向圖（不一定連通）。

一個帶标号的圖的價值定義為每個點度數的k次方的和。

給定n和k，請計算所有n個點的帶标号的簡單無向圖的價值之和。

因為答案很大，請對998244353取模輸出。

Solution

考慮每個點的貢獻，容易得到如下式子： a n s = n × 2 n ( n − 1 ) 2 − n + 1 ∑ i = 1 n − 1 C n − 1 i i k ans=n\times2^{{n(n-1)\over2}-n+1}\sum_{i=1}^{n-1}C_{n-1}^ii^k ans=n×22n(n−1)​−n+1i=1∑n−1​Cn−1i​ik

前面的一堆很好算，先丢掉，考慮後面的怎麼求。試着用第二類斯特林數把後面的 i k i^k ik展開一下： ∑ i = 1 n − 1 C n − 1 i ∑ j = 1 m i n ( n , k ) S ( k , j ) C i j j ! \sum_{i=1}^{n-1}C_{n-1}^i\sum_{j=1}^{min(n,k)}S(k,j)C_i^jj! i=1∑n−1​Cn−1i​j=1∑min(n,k)​S(k,j)Cij​j!交換求和順序： ∑ j = 1 k S ( k , j ) j ! ( ∑ i ≥ j C n − 1 i C i j ) \sum_{j=1}^kS(k,j)j!(\sum_{i\ge j} C_{n-1}^iC_i^j) j=1∑k​S(k,j)j!(i≥j∑​Cn−1i​Cij​)

此時發現不會搞了，考慮後面那個東西的組合意義：先從 n − 1 n-1 n−1個中選出 j j j個，然後剩下的選不選都可以。是以後面的那堆其實等于： C n − 1 j 2 n − 1 − j C_{n-1}^j2^{n-1-j} Cn−1j​2n−1−j

然後我們用容斥求第二類斯特林數的那個式子，用NTT先算出斯特林數，然後再算這個式子就可以了。

Code

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define pa pair<int,int>
const int Maxn=200010;
const int inf=2147483647;
const int mod=998244353,gn=3;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return x*f;
}
void upd(int&x,int y){x+=y;if(x>=mod)x-=mod;}
void cmin(int&x,int y){x=min(x,y);}
void cmax(int&x,int y){x=max(x,y);}
int n,k,A[Maxn<<2],B[Maxn<<2];
int Pow(int x,LL y)
{
    if(!y)return 1;
    int t=Pow(x,y>>1),re=(LL)t*t%mod;
    if(y&1)re=(LL)re*x%mod;
    return re;
}
int fac[Maxn],fin[Maxn];
void pre()
{
    fac[0]=1;for(int i=1;i<=k;i++)fac[i]=(LL)fac[i-1]*i%mod;
    fin[k]=Pow(fac[k],mod-2);for(int i=k-1;i>=0;i--)fin[i]=(LL)fin[i+1]*(i+1)%mod;
}
int C(int n,int m)
{
    if(n<m)return 0;
    return(LL)fac[n]*fin[m]%mod*fin[n-m]%mod;
}
int rev[Maxn<<2];
void NTT(int *a,int n,int o)
{
    for(int i=0;i<n;i++)if(i<rev[i])swap(a[i],a[rev[i]]);
    for(int i=1;i<n;i<<=1)
    {
        int wn;
        if(o==1)wn=Pow(gn,(mod-1)/(i<<1));
        else wn=Pow(gn,mod-1-(mod-1)/(i<<1));
        for(int j=0;j<n;j+=(i<<1))
        {
            int w=1;
            for(int k=0;k<i;k++)
            {
                int t=(LL)a[i+j+k]*w%mod;w=(LL)w*wn%mod;
                a[i+j+k]=(a[j+k]-t+mod)%mod;
                a[j+k]=(a[j+k]+t)%mod;
            }
        }
    }
    if(o==-1)
    {
        int inv=Pow(n,mod-2);
        for(int i=0;i<n;i++)a[i]=(LL)a[i]*inv%mod;
    }
}
int main()
{
    n=read(),k=read();k=min(k,n);
    pre();
    int m=1;while(m<=((k+1)<<1))m<<=1;
    rev[0]=0;for(int i=1;i<m;i++)rev[i]=((rev[i>>1]>>1)|((i&1)*(m>>1)));
    for(int i=0;i<=k;i++)
    if(i&1)A[i]=mod-fin[i];
    else A[i]=fin[i];
    for(int i=0;i<=k;i++)B[i]=(LL)Pow(i,k)*fin[i]%mod;
    NTT(A,m,1),NTT(B,m,1);
    for(int i=0;i<m;i++)A[i]=(LL)A[i]*B[i]%mod;
    NTT(A,m,-1);
    int ans=0,C=n-1;
    for(int i=1;i<=k;i++)
    {
        upd(ans,(LL)A[i]*fac[i]%mod*C%mod*Pow(2,n-1-i)%mod);
        C=(LL)C*(n-i-1)%mod;
        C=(LL)C*Pow(i+1,mod-2)%mod;
    }
    ans=(LL)ans*n%mod;
    LL t=(LL)n*(n-1)/2LL-n+1LL;
    ans=(LL)ans*Pow(2,t)%mod;
    printf("%d",ans);
}