C. Trees of Tranquillity
D. It's a bird! No, it's a plane! No, it's AaParsa!
E. Mashtali and Hagh Trees
F. AmShZ Farm
先不考虑那个 \(k\) 次幂，问题变得十分经典。有一排 \(n\) 个座位，每个人一开始有一个想坐的座位，依次入座，若已占便找后面第一个空位，求满座方案数。
考虑加一个点 \(n+1\)，改为在环上走，则最后每个座位被占概率均等，不合法的就是一开始选了 \(n+1\) 或者最后占了 \(n+1\)，注意到一开始有 \(n+1\) 的话最后一定会占掉 \(n+1\)，所以就是 \(\frac 1{n+1}\) 的概率不合法，方案数为 \((n+1)^{n-1}\)。也可以这么理解，即对于每一种方案，每个人向后循环平移相同长度，这 \(n+1\) 种方案中，有且仅有一种空出来的位置为 \(n+1\)。于是我们可以对于所有方案计数最后除以 \(n+1\) 即可。
现在考虑这个幂次。对于 \(1\) 到 \(n+1\) 的每一种颜色，单独考虑它的贡献，枚举其出现次数，即 \(\sum \limits_{i=0}^{n} i^k\binom{n}{i} n^{n-i}\)
到这里本题几乎就做完了，接下来就是套路的斯特林数操作，本题解略去。
#include<bits/stdc++.h>
using namespace std;
#define inf 1e9
const int maxn=1e6+10;
const int mod=998244353;
const int G=3;
const int iG=(mod+1)/3;
inline int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}
int n,k,fac[maxn],ifc[maxn],inv[maxn],ans,tr[maxn];
inline int ksm(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;
}
inline void ntt(int *f,int len,int flag){
for(int i=0;i<len;i++)
if(i<tr[i])swap(f[i],f[tr[i]]);
for(int i=2;i<=len;i<<=1){
int l=i/2,w=ksm(flag?G:iG,(mod-1)/i);
for(int j=0;j<len;j+=i){
int wi=1;
for(int k=j;k<j+l;k++){
int t=1ll*wi*f[k+l]%mod;
f[k+l]=(f[k]-t+mod)%mod;
f[k]=(f[k]+t)%mod;
wi=1ll*wi*w%mod;
}
}
}
if(!flag){
int iv=ksm(len,mod-2);
for(int i=0;i<len;i++)
f[i]=1ll*f[i]*iv%mod;
}
}
int a[maxn],b[maxn];
int main(){
n=read(),k=read();
inv[1]=fac[0]=ifc[0]=1;
for(int i=2;i<=k;i++)
inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
for(int i=1;i<=k;i++)
fac[i]=1ll*fac[i-1]*i%mod;
for(int i=1;i<=k;i++)
ifc[i]=1ll*ifc[i-1]*inv[i]%mod;
for(int i=0;i<=k;i++)
a[i]=1ll*ifc[i]*ksm(i,k)%mod;
for(int i=0;i<=k;i++)
b[i]=((i&1)?mod-ifc[i]:ifc[i]);
int len=1;for(;len<=k+k;len<<=1);
for(int i=0;i<len;i++)
tr[i]=(tr[i>>1]>>1)|((i&1)?len>>1:0);
ntt(a,len,1),ntt(b,len,1);
for(int i=0;i<len;i++)
a[i]=1ll*a[i]*b[i]%mod;
ntt(a,len,0);
for(int i=0,w=1;i<=k&&i<=n;i++){
ans=(ans+1ll*a[i]*w%mod*ksm(1+n,n-i))%mod;
w=1ll*w*(n-i)%mod;
}printf("%d\n",ans);
return 0;
}//