定义有向图的价值为图中每一个点的度数的 \(k\) 次方之和.
求：对于 \(n\) 个点的无向图所有可能情况的图的价值之和.
遇到这种题，八成是每个点单独算贡献，然后累加起来.
我们可以枚举一个点的度数是多少，然后试着去算该情况下的贡献，即 \(\sum_{i=0}^{n-1}\binom{n-1}{i}i^k\)
由于一共有 \(n\) 个点，而除了我们限定的边之外其余的边都是可以随便连的.
故 \(Ans=n\times 2^{\frac{(n-1)(n-2)}{2}}\times \sum_{i=0}^{n-1}\binom{n-1}{i}i^k\)
前面的好算，关键在于后面的 \(\sum_{i=0}^{n-1}\binom{n-1}{i}i^k\)
考虑将 \(i^k\) 按照第二类斯特林数的方式展开，得 \(\sum_{i=0}^{n-1}\sum_{j=0}^{i}S(k,j)\binom{i}{j}(j!)\)
考虑提前枚举 \(j\)，有 \(\sum_{j=0}^{n-1}S(k,j)(j!)\sum_{i=j}^{n-1}\binom{n-1}{i}\binom{i}{j}\)
后面那个 \(\sum_{i=j}^{n-1}\binom{n-1}{i}\binom{i}{j}\) 还可以继续推，将组合数变换一下，有 \(\sum_{i=j}^{n-1}\binom{n-1}{j}\binom{n-1-j}{i-j}\)
\(\Rightarrow \binom{n-1}{j}\sum_{i=j}^{n-1}\binom{n-1-j}{i-j}\)
然后 \(\sum_{i=j}^{n-1}\binom{n-1-j}{i-j}\) 的组合意义是从 \(n-1-j\) 个元素中选择有标号的 \(0,1,2...n-1-j\) 个元素的方案数.
这个直接就可以写成 \(2^{n-1-j}\)
故 \(Ans=n\times 2^{\frac{(n-1)(n-2)}{2}}\sum_{j=0}^{n-1}S(k,j)(j!)\binom{n-1}{j}2^{n-1-j}\)
由于 \(j\leqslant k\) 时斯特林数才有意义，所以我们只需枚举到 \(min(k,n-1)\) 即可.
斯特林数要用 NTT 来预处理.
#include <bits/stdc++.h>
#define LL long long
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
const int G=3,mod=998244353,N=400005,phi=998244352;
inline int qpow(int x,int y)
{
int tmp=1;
for(;y;y>>=1,x=1ll*x*x%mod) if(y&1) tmp=1ll*tmp*x%mod;
return tmp;
}
inline int INV(int x) { return qpow(x,mod-2); }
inline void NTT(int *a,int len,int flag)
{
int i,j,k,mid;
for(i=k=0;i<len;++i)
{
if(i>k) swap(a[i],a[k]);
for(j=len>>1;(k^=j)<j;j>>=1);
}
for(mid=1;mid<len;mid<<=1)
{
int wn=qpow(G,(mod-1)/(mid<<1));
if(flag==-1) wn=INV(wn);
for(i=0;i<len;i+=mid<<1)
{
int w=1;
for(j=0;j<mid;++j)
{
int x=a[i+j],y=1ll*w*a[i+j+mid]%mod;
a[i+j]=1ll*(x+y)%mod, a[i+j+mid]=1ll*(x-y+mod)%mod;
w=1ll*w*wn%mod;
}
}
}
if(flag==-1)
{
int rev=INV(len);
for(i=0;i<len;++i) a[i]=1ll*a[i]*rev%mod;
}
}
int f[N<<2],g[N<<2],fac[N],inv[N];
void Initialize(int Lim)
{
int i,j,limit;
inv[0]=fac[0]=1;
for(i=1;i<=Lim;++i) fac[i]=1ll*fac[i-1]*i%mod,inv[i]=INV(fac[i]);
for(i=0;i<=Lim;++i)
{
f[i]=inv[i];
if(i&1) f[i]=mod-f[i];
g[i]=1ll*inv[i]*qpow(i,Lim)%mod;
}
for(limit=1;limit<=2*(Lim+1);limit<<=1);
NTT(f,limit,1),NTT(g,limit,1);
for(i=0;i<limit;++i) f[i]=1ll*f[i]*g[i]%mod;
NTT(f,limit,-1);
}
int main()
{
// setIO("input");
int i,j,n,k,ans=0,Lim;
scanf("%d%d",&n,&k),Lim=min(n-1,k);
Initialize(k);
int now=1,tot=n-1;
for(i=0;i<=Lim;++i)
{
int delta=1ll*f[i]*now%mod*qpow(2,n-1-i)%mod;
ans=(ans+delta)%mod;
now=1ll*now*tot%mod;
--tot;
}
ans=1ll*ans*n%mod;
ans=1ll*ans*qpow(2,1ll*(n-1)*(n-2)/2%phi)%mod;
printf("%d\n",ans);
return 0;
}