[cf1528F]AmShZ Farm

考虑$a_{i}$是"more-equal"的组合意义，有以下构造——

有$n$个位置，每一次选择一个位置$a_{i}$，在$a_{i}$之后（包括$a_{i}$）的第一个空位上停一辆车，那么$a_{i}$即要求每一辆车都可以停（不存在停到第$n+1$个位置及以后的情况）

关于这个问题，可以在之后新增一个位置，并将整个序列变成一个环，那么方案合法当且仅当第$n+1$个位置没有车，由于每一个位置没车的概率相同，即有$(n+1)^{n-1}$种方案

接下来，即对于每一组方案，令$tot_{i}=sum_{1le jle 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}{nchoose i}i^{k}n^{n-i}$种方案

将$i^{k}$用第二类斯特林数来计算，即$sum_{i=1}^{n}{nchoose i}n^{n-i}sum_{j=0}^{i}{ichoose 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-jchoose 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}{mchoose i}(m-i)^{n}=sum_{i=0}^{m}frac{(-1)^{i}}{i!}frac{(m-i)^{n}}{(m-i)!}$，直接ntt即可

时间复杂度为$o(klog k)$，可以通过

#include<bits/stdc++.h>
using namespace std;
#define N (1<<18)
#define M 100005
#define mod 998244353
int n,k,ans,rev[N],a[N],b[N],fac[M],inv[M];
int qpow(int n,int m){
    int s=n,ans=1;
    while (m){
        if (m&1)ans=1LL*ans*s%mod;
        s=1LL*s*s%mod;
        m>>=1;
    }
    return ans;
}
void ntt(int *a,int p){
    for(int i=0;i<N;i++)
        if (i<rev[i])swap(a[i],a[rev[i]]);
    for(int i=2;i<=N;i<<=1){
        int s=qpow(3,(mod-1)/i);
        if (p)s=qpow(s,mod-2);
        for(int j=0;j<N;j+=i)
            for(int k=0,ss=1;k<(i>>1);k++,ss=1LL*ss*s%mod){
                int x=a[j+k],y=1LL*ss*a[j+k+(i>>1)]%mod;
                a[j+k]=(x+y)%mod;
                a[j+k+(i>>1)]=(x-y+mod)%mod; 
            }
    }
    if (p){
        int s=qpow(N,mod-2);
        for(int i=0;i<N;i++)a[i]=1LL*a[i]*s%mod;
    }
}
int main(){
    scanf("%d%d",&n,&k);
    fac[0]=inv[0]=inv[1]=1;
    for(int i=1;i<M;i++)fac[i]=1LL*fac[i-1]*i%mod;
    for(int i=2;i<M;i++)inv[i]=1LL*(mod-mod/i)*inv[mod%i]%mod;
    for(int i=1;i<M;i++)inv[i]=1LL*inv[i-1]*inv[i]%mod;
    for(int i=0;i<N;i++)rev[i]=(rev[i>>1]>>1)+((i&1)<<17);
    for(int i=0;i<=k;i++){
        a[i]=inv[i];
        if (i&1)a[i]=mod-a[i];
    }
    for(int i=0;i<=k;i++)b[i]=1LL*qpow(i,k)*inv[i]%mod;
    ntt(a,0);
    ntt(b,0);
    for(int i=0;i<N;i++)a[i]=1LL*a[i]*b[i]%mod;
    ntt(a,1);
    int s=1;
    for(int i=0;i<=min(n,k);i++){
        ans=(ans+1LL*s*qpow(n+1,n-i)%mod*a[i])%mod;
        s=1LL*s*(n-i)%mod;
    }
    printf("%d",ans);
}