bzoj 5093 [Lydsy1711月赛]图的价值 NTT+第二类斯特林数

[Lydsy1711月赛]图的价值

Time Limit: 30 Sec  Memory Limit: 256 MB
Submit: 245  Solved: 128
[Submit][Status][Discuss]

Description

“简单无向图”是指无重边、无自环的无向图（不一定连通）。

一个带标号的图的价值定义为每个点度数的k次方的和。

给定n和k，请计算所有n个点的带标号的简单无向图的价值之和。

因为答案很大，请对998244353取模输出。

 

Input

第一行包含两个正整数n,k(1<=n<=10^9,1<=k<=200000)。

 

Output

输出一行一个整数，即答案对998244353取模的结果。

 

Sample Input

6 5

Sample Output

67584000

HINT

 

Source

本OJ付费获取

因为第二类斯特林数m>n的时候为0，所以就优化成，k log k了，主要就是计算第二类斯特林数，后面组合那里因为最多k

所以就是n-k+1项的反过来乘就可以处理了，然后还有ksm一下。

 #include<cstring>

 #include<cstdio>

 #include<iostream>

 #include<algorithm>

 #include<cmath>

 #define ll long long

 #define mod 998244353

 #define G 3

 #define N 200007

 using namespace std;

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while(!isdigit(ch)){if(ch=='-')f=-;ch=getchar();}

     while(isdigit(ch)){x=(x<<)+(x<<)+ch-'';ch=getchar();}

     return x*f;

 }

 int n,k,num,L,ans,inv;

 int jc[N],jcf[N],ny[N];

 int a[N<<],b[N<<],rev[N<<];

 int ksm(int a,ll b)

 {

     int ans=;

     while(b)

     {

         if (b&) ans=(ll)ans*a%mod;

         a=(ll)a*a%mod;

         b>>=;

     }

     return ans;

 }

 void init()

 {

     jc[]=jcf[]=ny[]=;

     for (int i=;i<=k;i++)

         jc[i]=(ll)jc[i-]*i%mod,ny[i]=ksm(i,mod-),ny[i]=(ll)ny[i]*ny[i-]%mod;

     for (int i=;i<=k;i++)

         a[i]=1ll*((i&)?(-):)*ny[i],b[i]=(ll)ksm(i,k)*ny[i]%mod;

     for (int i=;i<=k;i++) jcf[i]=(ll)jcf[i-]*(n-i+)%mod;

     for (num=;num<=k*;num<<=,L++);if (L) L--;

     inv=ksm(num,mod-);

     for (int i=;i<num;i++)

         rev[i]=(rev[i>>]>>)|((i&)<<L);

 }

 void NTT(int *a,int flag)

 {

     for (int i=;i<num;i++)

         if (i<rev[i]) swap(a[i],a[rev[i]]);

     for (int i=;i<num;i<<=)

     {

         int wn=ksm(G,(mod-)/(i<<));

         for (int j=;j<num;j+=(i<<))

         {

             int w=;

             for (int k=;k<i;w=(ll)w*wn%mod,k++)

             {

                 int x=a[j+k],y=(ll)w*a[j+k+i]%mod;

                 a[j+k]=(x+y)%mod,a[j+k+i]=(x-y<)?x-y+mod:x-y;

             }

         }

     }

     if (flag==-)

     {

         for (int i=;i<num/;i++) swap(a[i],a[num-i]);

         for (int i=;i<num;i++) a[i]=(ll)a[i]*inv%mod;

     }

 }

 int main()

 {

     n=read(),k=read(),n--;

     init();

     NTT(a,),NTT(b,);

     for (int i=;i<num;i++)

         a[i]=(ll)a[i]*b[i]%mod;

     NTT(a,-);

     for (int i=;i<=min(n,k);i++)

         (ans+=(ll)a[i]*jc[i]%mod*ksm(,n-i)%mod*jcf[i]%mod*ny[i]%mod)%=mod;

     ans=(ll)ans*(n+)%mod*ksm(,(ll)(n-)*n/)%mod;

     printf("%d\n",ans);

 }