bzoj 5093: [Lydsy1711月赛]图的价值

5093: [Lydsy1711月赛]图的价值

Time Limit: 30 Sec  Memory Limit: 256 MB
Submit: 230  Solved: 123
[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付费获取

 

    通过枚举每个节点的贡献，我们可以得出: ANS = N * 2^((N-1)*(N-2)/2) * ΣC(N-1,i) * i^K

显然Σ前面的可以直接提出来，后面的就是某道 codeforces E 题(貌似叫 Team Work)的加强版。

    想看接下来的推导的同学可以直接转到那个题233 (http://www.cnblogs.com/JYYHH/p/8450199.html)

    最后推完的式子就是 Σ S(K,i) * P(N,i) * 2^(N-i) ，在那个题里说了其实K出到10^5级别也是可以做的，用的就是 今天学的斯特林反演，这里也就不再推了，上一个博客刚刚写完一个斯特林反演23333。我们直接用NTT就可以求出第K行的所有斯特林数然后带进去直接算就行了。

 

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=660005;
const int ha=998244353;
const int root=3,inv=ha/3+1;
int a[maxn],b[maxn],jc[maxn];
int r[maxn],N,M,n,INV,l,K;

inline int add(int x,int y){
	x+=y;
	return x>=ha?x-ha:x;
}

inline int ksm(int x,int y){
	int an=1;
	for(;y;y>>=1,x=x*(ll)x%ha) if(y&1) an=an*(ll)x%ha;
	return an;
}

inline void NTT(int *c,const int f){
	for(int i=0;i<N;i++) if(i<r[i]) swap(c[i],c[r[i]]);
	
	for(int i=1;i<N;i<<=1){
		int omega=ksm(f==1?root:inv,(ha-1)/(i<<1));
		for(int p=i<<1,j=0;j<N;j+=p){
			int now=1;
			for(int k=0;k<i;k++,now=now*(ll)omega%ha){
				int x=c[j+k],y=c[j+k+i]*(ll)now%ha;
				c[j+k]=add(x,y);
				c[j+k+i]=add(x,ha-y);
			}
		}
	}
	
	if(f==-1) for(int i=0;i<N;i++) c[i]=c[i]*(ll)INV%ha;
}

inline void init(){
	jc[0]=1;
	for(int i=1;i<=K;i++) jc[i]=jc[i-1]*(ll)i%ha;
	for(int i=0;i<=K;i++){
		a[i]=ksm(i,K)*(ll)ksm(jc[i],ha-2)%ha;
		if(i&1) b[i]=ha-ksm(jc[i],ha-2);
		else b[i]=ksm(jc[i],ha-2);
	}
	M=K<<1;
	for(N=1;N<=M;N<<=1) l++;
	for(int i=0;i<N;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
}

inline int solve(){
	int ans=0;
	init();
	
	NTT(a,1),NTT(b,1);
	for(int i=0;i<N;i++) a[i]=a[i]*(ll)b[i]%ha;
	INV=ksm(N,ha-2),NTT(a,-1);
	
	int base=1;
	for(int i=0;i<=K;base=base*(ll)(n-i)%ha,i++){
		ans=add(ans,a[i]*(ll)base%ha*(ll)ksm(2,n-i)%ha);
	}
	return ans;
}

int main(){
	scanf("%d%d",&n,&K),n--;
	printf("%d
",solve()*(ll)(n+1)%ha*(ll)ksm(2,n*(ll)(n-1)/2%(ha-1))%ha);
	return 0;
}