BZOJ5093 图的价值

Solution

先审对题，图并不要求联通，那么有：

[ans=nsum_{i=1}^{n-1} i^kinom {n-1} i 2^{frac{(n-1)(n-2)} 2} ]

把后面的提到前面，得到 (Codeforces932E)

那么套上式子：

[sum_{i=1}^n inom n i i^k=sum_{i=1}^k 2^{n-i} inom n i S(k,i) imes i! ]

求一行用 (NTT) 即可

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define reg register
namespace yspm{
    inline int read(){
        int res=0,f=1; char k;
        while(!isdigit(k=getchar())) if(k=='-') f=-1;
        while(isdigit(k)) res=res*10+k-'0',k=getchar();
        return res*f;
    }
    const int mod=998244353,N=6e5+10;
    inline int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
    inline int del(int x,int y){return x-y<0?x-y+mod:x-y;}
    inline int mul(int x,int y){return x*y-x*y/mod*mod;}
    inline int ksm(int x,int y){int res=1; for(;y;y>>=1,x=mul(x,x)) if(y&1) res=mul(res,x); return res;}
    int fac[N],inv[N],n,k,r[N];
    inline void NTT(int *f,int lim,int fl){
        for(reg int i=0;i<lim;++i) r[i]=r[i>>1]>>1|((i&1)?(lim>>1):0);
        for(reg int i=0;i<lim;++i) if(i<r[i]) swap(f[i],f[r[i]]); 
        for(reg int p=2;p<=lim;p<<=1){
            int len=p>>1,tmp=ksm(3,(mod-1)/p); if(fl==-1) tmp=ksm(tmp,mod-2);
            for(reg int k=0;k<lim;k+=p){
                int buf=1; for(reg int l=k;l<k+len;++l){
                    int tt=mul(buf,f[l+len]); f[l+len]=del(f[l],tt); f[l]=add(f[l],tt); 
                    buf=mul(buf,tmp);           
                }
            }
        } if(fl==-1) for(reg int i=0;i<lim;++i) f[i]=mul(f[i],ksm(lim,mod-2)); return ;
    }
    int A[N],B[N],S[N];
    inline void Str(int n){
        for(reg int i=0;i<=n;++i) A[i]=mul((i&1)?mod-1:1,inv[i]),B[i]=mul(ksm(i,n),inv[i]);
        int lim=1; while(lim<=(n<<1)) lim<<=1; NTT(A,lim,1); NTT(B,lim,1); 
        for(reg int i=0;i<lim;++i) S[i]=mul(A[i],B[i]); NTT(S,lim,-1);
        return ;
    }
    signed main(){
        n=read(); k=read(); fac[0]=fac[1]=inv[0]=inv[1]=1; for(reg int i=2;i<N;++i) fac[i]=mul(i,fac[i-1]),inv[i]=mod-mul(mod/i,inv[mod%i]);  
        for(reg int i=1;i<N;++i) inv[i]=mul(inv[i],inv[i-1]); Str(k); 
        int ans=0,bas=mul(n,ksm(2,(n-2)*(n-1)/2)),cur=n-1; 
        for(reg int i=1;i<=min(n-1,k);++i,cur=mul(cur,n-i)) ans=add(ans,mul(S[i],mul(cur,ksm(2,n-i-1))));
        printf("%lld
",mul(ans,bas));
        return 0;
    }
}
signed main(){return yspm::main();}

审对了题就很简单了