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
Sol
首先我们发现，图中每个点的贡献是独立的，而且每个点都一样，所以我们只计算1号点的贡献，之后乘n即可。除了1号点，其他的点可以任意连边，而1号点的出边有n-1条，我们可以枚举选择几条，于是有：
\(ans=n*2^{\frac{(n-1)(n-2)}{2}}*\sum_{i=0}^{n-1}C_n^i*i^k\)
前面一部分显然能够直接算，然后我们把n--，考虑后面一部分：
有这样一个定理：\(n^k=\sum_{i=1}^{n}A_n^iS_k^i\)，证明的话，可以用组合意义证明，就是考虑把k个球放到n个带标号的箱子的方案数，显然两边都可以描述这样的方案数。
所以\(\sum_{i=0}^{n}C_n^i*i^k=\sum_{i=0}^{n}C_n^i*\sum_{j=0}^{i}A_i^jS_k^j\)
\(=\sum_{i=0}^{n}C_n^i*\sum_{j=0}^iC^j_ij!S_k^j\)
\(=\sum_{j=0}^{n}j!S_k^j\sum_{i=0}^nC_n^iC_i^j\)
这里因为组合数的限制，我们可以把求和上限取到n，不会影响答案，但是这样便于进一步的推导。
后面那个式子等同于\(C_n^j*2^{n-j}\)，因为从n个中选i个，再从i中选j个，而且i是从1~n循环的，这等同于我们直接枚举j，然后剩下的随意选与不选的方案数，也就是上面的式子了。
这样原式\(=\sum_{j=0}^nj!S_k^jC_n^j*2^{n-j}\)
斯特林数因为下底固定，所以可以用NTT计算，然后这个题就能在\(O(nlogn)\)时间内解决。
要注意\(C_n^j\)因为下底过大无法预处理，所以只能按步根据定义式计算。
Code
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n,fac[200005],ifa[200005],inv[200005],a[524289],b[524289],C=1,P=998244353,w,wn,t,ans;int K,len,i,j,k;
ll ksm(ll a,ll b){ll res=1;for(;b;b>>=1,a=a*a%P) if(b&1) res=res*a%P;return res;}
void ntt(ll *a,int n,int op)
{
for(i=k=0;i<n;i++){if(i>k) swap(a[i],a[k]);for(j=(n>>1);(k^=j)<j;j>>=1);}
for(k=2,wn=ksm(3,op==1?(P-1)/k:P-1-(P-1)/k);k<=n;k<<=1,wn=ksm(3,op==1?(P-1)/k:P-1-(P-1)/k))
for(i=0,w=1;i<n;i+=k,w=1) for(j=0;j<(k>>1);j++,w=w*wn%P)
t=a[i+j+(k>>1)]*w%P,a[i+j+(k>>1)]=(a[i+j]-t+P)%P,a[i+j]=(a[i+j]+t)%P;
if(op==-1) for(t=ksm(n,P-2),i=0;i<n;i++) a[i]=a[i]*t%P;
}
int main()
{
scanf("%lld%d",&n,&K);n--;
for(len=1;len<=(K*2);len<<=1);
inv[0]=inv[1]=fac[0]=fac[1]=ifa[0]=ifa[1]=1;
for(int i=2;i<=K;i++) inv[i]=P-(P/i)*inv[P%i]%P,fac[i]=fac[i-1]*i%P,ifa[i]=inv[i]*ifa[i-1]%P;
for(int i=0;i<=K;i++) a[i]=(i&1?-1:1)*ifa[i],b[i]=ksm(i,K)*ifa[i]%P;
ntt(a,len,1);ntt(b,len,1);
for(int i=0;i<len;i++) a[i]=a[i]*b[i]%P;ntt(a,len,-1);
for(int i=0;i<=n&&i<=K;i++) ans=(ans+a[i]*fac[i]%P*C%P*ksm(2,n-i)%P)%P,C=C*(n-i)%P*inv[i+1]%P;
ans=ans*(n+1)%P*ksm(2,n*(n-1)/2)%P;printf("%lld\n",(ans+P)%P);
}