Cptraser/ 三月 16, 2019/ 2019.3/ 0 comments

[Lydsy1711月赛]图的价值

考虑枚举点的度数,强制一个点的度数为i,那么答案为:

    \[n\sum_{i=0}^{n-1}2^{n-1\choose 2}{n-1\choose i}i^k\]

将要求和的部分单独提出来:

    \[\sum_{i=0}^{n-1}{n-1\choose i}i^k\]

i^k用第二类斯特林数展开:

    \[\sum_{i=0}^{n-1}{n-1\choose i}\sum_{j=0}^k S(k,j) j!{i\choose j}\]

交换枚举顺序(i小于j无意义):

    \[\sum_{j=0}^k S(k,j)j! \sum_{i=j}^{n-1}{n-1\choose i}{i\choose j}\]

考虑{n-1\choose i}{i\choose j}的组合意义,n-1个数里选择i个数,再在i个数里选择j个数的方案数。

那么可以改为:

    \[\sum_{j=0}^k S(k,j)j! \sum_{i=j}^{n-1}{n-1\choose j}{n-1-j\choose i-j}\]

考虑改为枚举i-j

    \[\sum_{j=0}^k S(k,j)j! {n-1\choose j} \sum_{i=0}^{n-1-j}{n-1-j\choose i}\]

然后二项式定理即可:

    \[\sum_{j=0}^{min(n-1,k)} S(k,j)j! {n-1\choose j} 2^{n-1-j}\]

所以我们只要用FFT处理出S(k,1)...S(k,k)即可。

这道题n范围比较大所以组合数一边做一边处理。

#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long LL;
const int Mod=998244353,Maxn=2e6+5;
int Ksm(int x,long long y){int res=1;for(;y;y>>=1,x=(LL)x*x%Mod)if(y&1)res=(LL)res*x%Mod;return res;}
const int g=3,invg=332748118;

int N,K,F[Maxn],G[Maxn],len=1,L,r[Maxn];
long long Fac[Maxn],Inv[Maxn],Ans=0;

void NTT(int *A,int Opt){
    for(int i=0;i<len;i++)if(i<r[i])swap(A[i],A[r[i]]);
    for(int i=1;i<len;i<<=1){
        long long Wn=Ksm(Opt>0?g:invg,(Mod-1)/(i<<1));
        for(int j=0;j<len;j+=(i<<1)){
            long long w=1;
            for(int k=0;k<i;k++,w=w*Wn%Mod){
                long long x=A[j+k],y=w*A[i+j+k]%Mod;
                A[j+k]=(x+y)%Mod,A[i+j+k]=(x-y+Mod)%Mod;
            }
        }
    }if(Opt<0)for(int i=0,inv=Ksm(len,Mod-2);i<len;i++)A[i]=(LL)A[i]*inv%Mod;
}

int C(int x,int y){
    return (x<y)?0:(Fac[x]*Inv[y]%Mod*Inv[x-y]%Mod);
}
int main()
{
    scanf("%d%d",&N,&K),Fac[0]=1;
    for(int i=1;i<=K;i++)Fac[i]=Fac[i-1]*i%Mod;
    for(int i=0;i<=K;i++)Inv[i]=Ksm(Fac[i],Mod-2);
    for(int i=0;i<=K;i++)F[i]=(LL)(i&1?(Mod-1):1)*Inv[i]%Mod;
    for(int i=0;i<=K;i++)G[i]=(LL)Ksm(i,K)*Inv[i]%Mod;
    while(len<=(K<<1))len<<=1,++L;
    for(int i=0;i<len;i++)r[i]=(r[i>>1]>>1)|((i&1)<<(L-1));
    NTT(F,1),NTT(G,1);
    for(int i=0;i<len;i++)F[i]=(LL)F[i]*G[i]%Mod;
    NTT(F,-1);long long Cn=1;
    for(int i=0;i<=min(N-1,K);i++){
        Ans=(Ans+F[i]*Fac[i]%Mod*Cn%Mod*Ksm(2,N-1-i)%Mod)%Mod;
        Cn=(LL)Cn*(N-1-i)%Mod*Ksm(i+1,Mod-2)%Mod;
    }printf("%lld",Ans*N%Mod*Ksm(2,(LL)(N-2)*(N-1)/2)%Mod);
}
Share this Post

Leave a Comment

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

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>
*
*