本文共 3389 字，大约阅读时间需要 11 分钟。

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

题解

一般都要单独考虑一个点的贡献
显然这个点的贡献是独立的，最后乘一个n就可以
那单独一个点的贡献就是
$$\sum _{i=1}^{n-1}{C}_{n-1}^i\ast 2^{\frac{(n-1)(n-2)}{2}}\ast i^k$$
2的次幂是常数，提到前面去，把n减一，显然我们只需要算
$$\sum _{i=1}^n{C}_n^i\ast i^k$$
根据第二类斯特林数的性质，我们可以知道
$$\sum _{i=1}^n{C}_n^i\sum _{j=0}^{min(i,k)}S(k,j)\ast j!\ast C_i^j$$
乘法分配律一下，显然可以把斯特林数提前
$$\sum _{i=0}^{min(n,k)}S(k,i)\ast i!\ast \sum _{j=i}^n{C}_n^j\ast C_j^i$$
后面的式子的意义就是在n中选i个数，其它可选可不选，所以就是
$$\sum _{i=0}^{min(n,k)}S(k,i)\ast i!\ast C_n^i\ast 2^{n-i}$$
现在就是要算前面的斯特林数了
可以容斥然后NTT$nlogn$求，点一下就知道啦

#include<cstdio>#include<cstring>#include<cstdlib>#include<algorithm>#include<cmath>#include<queue>#include<vector>#include<ctime>#include<map>#include<bitset>#define LL long long#define mp(x,y) make_pair(x,y)#define pll pair<long long,long long>#define pii pair<int,int>using namespace std;inline LL read(){   	LL f=1,x=0;char ch=getchar();	while(ch<'0'||ch>'9'){   if(ch=='-')f=-1;ch=getchar();}	while(ch>='0'&&ch<='9'){   x=x*10+ch-'0';ch=getchar();}	return x*f;}int stack[20];inline void write(int x){   	if(x<0){   putchar('-');x=-x;}    if(!x){   putchar('0');return;}    int top=0;    while(x)stack[++top]=x%10,x/=10;    while(top)putchar(stack[top--]+'0');}inline void pr1(int x){   write(x);putchar(' ');}inline void pr2(int x){   write(x);putchar('\n');}const LL mod=998244353;const int MAXN=200005;LL pow_mod(LL a,LL b){   	LL ret=1;	while(b)	{   		if(b&1)ret=ret*a%mod;		a=a*a%mod;b>>=1;	}	return ret;}LL A[MAXN*4],B[MAXN*4];int R[MAXN*4],L;void NTT(LL *y,int len,int on){   	for(int i=0;i<len;i++)if(i<R[i])swap(y[i],y[R[i]]);	for(int i=1;i<len;i<<=1)	{   		LL wn=pow_mod(3,(mod-1)/(i*2));if(on==-1)wn=pow_mod(wn,mod-2);		for(int j=0;j<len;j+=(i<<1))		{   			LL w=1;			for(int k=0;k<i;k++)			{   				LL u=y[j+k];				LL v=y[j+k+i]*w%mod;				y[j+k]=(u+v)%mod;				y[j+k+i]=(u-v+mod)%mod;				w=w*wn%mod;			}		}	}	if(on==-1)	{   		LL temp=pow_mod(len,mod-2);		for(int i=0;i<len;i++)y[i]=y[i]*temp%mod;	}}int n,K;LL pre[MAXN],inv[MAXN];LL C[MAXN];void init(){   	C[0]=1;LL temp=1;	for(int i=1;i<=min(n,K);i++)	{   		temp=temp*(n-i+1)%mod;		temp=temp*pow_mod(i,mod-2)%mod;		C[i]=temp;	}}int main(){   	pre[0]=1;for(int i=1;i<=MAXN-5;i++)pre[i]=pre[i-1]*i%mod;	inv[MAXN-5]=pow_mod(pre[MAXN-5],mod-2);	for(int i=MAXN-6;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;	n=read();K=read();n--;	init();	int ln;	for(ln=1;ln<=2*K;ln<<=1)L++;	for(int i=0;i<ln;i++)R[i]=(R[i>>1]>>1)|(i&1)<<(L-1);	int temp=-1;	for(int i=0;i<=K;i++)	{   		temp*=-1;		A[i]=temp*inv[i]%mod;		LL u1=pow_mod(i,K),u2=inv[i];		B[i]=u1*u2%mod;	}	NTT(A,ln,1);NTT(B,ln,1);	for(int i=0;i<ln;i++)A[i]=A[i]*B[i]%mod;	NTT(A,ln,-1);	LL ans=0;	for(int i=0;i<=min(n,K);i++)	{   		LL re=A[i]*pre[i]%mod*C[i]%mod*pow_mod(2,n-i)%mod;		ans=(ans+re)%mod;	}	ans=ans*(n+1)%mod*pow_mod(2,(LL)(n)*(n-1)/2)%mod;	pr2(ans);	return 0;}

转载地址：http://immu.baihongyu.com/