BZOJ 5093: 图的价值 第二类斯特林数 NTT

#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<vector>
#include<string>
#include<bitset>
#include<queue>
#include<map>
#include<set>
using namespace std;

typedef long long ll;

inline int read()
{
    int x=0,f=1;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;
}
void print(int x)
{if(x<0)putchar('-'),x=-x;if(x>=10)print(x/10);putchar(x%10+'0');}

const int N=525000,mod=998244353;

inline int qpow(int x,int y)
{
	int res(1);
	while(y)
	{
		if(y&1) res=1ll*res*x%mod;
		x=1ll*x*x%mod;
		y>>=1;
	}
	return res;
}

int r[N];

void ntt(int *x,int lim,int opt)
{
	register int i,j,k,m,gn,g,tmp;
	for(i=0;i<lim;++i)
	{
		r[i]=(i&1)*(lim>>1)+(r[i>>1]>>1);
		if(r[i]<i) swap(x[i],x[r[i]]);
	}
	for(m=2;m<=lim;m<<=1)
	{
		k=m>>1;
		gn=qpow(3,(mod-1)/m);
		for(i=0;i<lim;i+=m)
		{
			g=1;
			for(j=0;j<k;++j,g=1ll*g*gn%mod)
			{
				tmp=1ll*x[i+j+k]*g%mod;
				x[i+j+k]=(x[i+j]-tmp+mod)%mod;
				x[i+j]=(x[i+j]+tmp)%mod;
			}
		}
	}
	if(opt==-1)
	{
		reverse(x+1,x+lim);
		int inv(qpow(lim,mod-2));
		for(i=0;i<lim;++i) x[i]=1ll*x[i]*inv%mod;
	}
}

int A[N],B[N],S[N];

int fac[N],inv[N];

int main()
{
	int n=read(),K=read();
	register int i,j,lim(1);
	fac[0]=1;for(i=1;i<=K;++i) fac[i]=1ll*fac[i-1]*i%mod;
	inv[1]=1;for(i=2;i<=K;++i) inv[i]=1ll*inv[mod%i]*(mod-mod/i)%mod;
	inv[0]=1;for(i=1;i<=K;++i) inv[i]=1ll*inv[i-1]*inv[i]%mod;
	
	for(i=0;i<=K;++i) A[i]=i&1 ? mod-inv[i] : inv[i];
	for(i=0;i<=K;++i) B[i]=1ll*qpow(i,K)*inv[i]%mod;
	
	while(lim<=(K<<1)) lim<<=1;
	ntt(A,lim,1);ntt(B,lim,1);
	for(i=0;i<lim;++i) S[i]=1ll*A[i]*B[i]%mod;
	ntt(S,lim,-1);
	
	int ans(0);
	for(i=0,j=1;i<=min(n-1,K);++i,j=1ll*j*(n-i)%mod)
		(ans+=1ll*S[i]*j%mod*qpow(2,n-i-1)%mod)%=mod;
	ans=1ll*ans*n%mod;
	ans=1ll*ans*qpow(2,(1ll*(n-1)*(n-2)>>1)%(mod-1))%mod;
	cout<<ans<<endl;
	return 0;
}