考虑$a_{i}$是"more-equal"的组合意义，有以下构造——
有$n$个位置，每一次选择一个位置$a_{i}$，在$a_{i}$之后（包括$a_{i}$）的第一个空位上停一辆车，那么$a_{i}$即要求每一辆车都可以停（不存在停到第$n+1$个位置及以后的情况）
关于这个问题，可以在之后新增一个位置，并将整个序列变成一个环，那么方案合法当且仅当第$n+1$个位置没有车，由于每一个位置没车的概率相同，即有$(n+1)^{n-1}$种方案
接下来，即对于每一组方案，令$tot_{i}=\sum_{1\le j\le n}[a_{j}=i]$，那么贡献即$\sum_{i=1}^{n}tot_{i}^{k}$
考虑枚举$i$和$tot_{i}$，那么即要求其中恰好$tot_{i}$次为$i$且第$n+1$个位置为空的方案数
由于$i$是任意的，可以看作对于所有$i$每一个位置没车的概率相同，也即有$\sum_{i=1}^{n}{n\choose i}i^{k}n^{n-i}$种方案
将$i^{k}$用第二类斯特林数来计算，即$\sum_{i=1}^{n}{n\choose i}n^{n-i}\sum_{j=0}^{i}{i\choose j}j!S(k,j)$（其中$S(n,m)$为第二类斯特林数）
将组合数展开并交换枚举顺序，即$\sum_{j=0}^{k}S(k,j)\sum_{i=1}^{n}\frac{n!n^{n-i}}{(i-j)!(n-i)!}$（显然当$n<m$时$S(n,m)=0$）
令$i‘=i-j$并构造最后一项为二项式展开，即$\sum_{j=0}^{k}\frac{n!}{(n-j)!}S(k,j)\sum_{i‘=0}^{n-j}{n-j\choose i‘}n^{n-j-i‘}$
根据二项式展开，即$\sum_{j=0}^{k}\frac{n!}{(n-j)!}(n+1)^{n-j}S(k,j)$
根据通项公式，即$S(n,m)=\frac{1}{m!}\sum_{i=0}^{m}(-1)^{i}{m\choose i}(m-i)^{n}=\sum_{i=0}^{m}\frac{(-1)^{i}}{i!}\frac{(m-i)^{n}}{(m-i)!}$，直接ntt即可
时间复杂度为$o(k\log k)$，可以通过
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N (1<<18) 4 #define M 100005 5 #define mod 998244353 6 int n,k,ans,rev[N],a[N],b[N],fac[M],inv[M]; 7 int qpow(int n,int m){ 8 int s=n,ans=1; 9 while (m){ 10 if (m&1)ans=1LL*ans*s%mod; 11 s=1LL*s*s%mod; 12 m>>=1; 13 } 14 return ans; 15 } 16 void ntt(int *a,int p){ 17 for(int i=0;i<N;i++) 18 if (i<rev[i])swap(a[i],a[rev[i]]); 19 for(int i=2;i<=N;i<<=1){ 20 int s=qpow(3,(mod-1)/i); 21 if (p)s=qpow(s,mod-2); 22 for(int j=0;j<N;j+=i) 23 for(int k=0,ss=1;k<(i>>1);k++,ss=1LL*ss*s%mod){ 24 int x=a[j+k],y=1LL*ss*a[j+k+(i>>1)]%mod; 25 a[j+k]=(x+y)%mod; 26 a[j+k+(i>>1)]=(x-y+mod)%mod; 27 } 28 } 29 if (p){ 30 int s=qpow(N,mod-2); 31 for(int i=0;i<N;i++)a[i]=1LL*a[i]*s%mod; 32 } 33 } 34 int main(){ 35 scanf("%d%d",&n,&k); 36 fac[0]=inv[0]=inv[1]=1; 37 for(int i=1;i<M;i++)fac[i]=1LL*fac[i-1]*i%mod; 38 for(int i=2;i<M;i++)inv[i]=1LL*(mod-mod/i)*inv[mod%i]%mod; 39 for(int i=1;i<M;i++)inv[i]=1LL*inv[i-1]*inv[i]%mod; 40 for(int i=0;i<N;i++)rev[i]=(rev[i>>1]>>1)+((i&1)<<17); 41 for(int i=0;i<=k;i++){ 42 a[i]=inv[i]; 43 if (i&1)a[i]=mod-a[i]; 44 } 45 for(int i=0;i<=k;i++)b[i]=1LL*qpow(i,k)*inv[i]%mod; 46 ntt(a,0); 47 ntt(b,0); 48 for(int i=0;i<N;i++)a[i]=1LL*a[i]*b[i]%mod; 49 ntt(a,1); 50 int s=1; 51 for(int i=0;i<=min(n,k);i++){ 52 ans=(ans+1LL*s*qpow(n+1,n-i)%mod*a[i])%mod; 53 s=1LL*s*(n-i)%mod; 54 } 55 printf("%d",ans); 56 }