题解：CF1349F1 Slime and Sequences (Easy Version)

被 x 老师瑞平之后突然有了新的想法。

在好序列出现的数显然是值域前缀；若设 a_i 为 i 的第一次出现位置，b_i 为末次出现位置。则限制形如：a_i\le b_i,a_i\le b_{i+1}。画图，每次让 a_i 跳到 b_{i+1} 连个正向的线，b_{i+1} 连个反线回到 a_{i+1}（第一条是 b_1\to a_1）。

这个转化不够好：即使得到图就连数出有多少序列都困难。但是对图做性质不变的修改：把中间出现的位置都用反边跳，即做 b_i\to ..\to a_i，这样就显然构成了一一对应。更好地，记下访问顺序，这就是排列。令此排列取其逆排列，这就得到了其他题解的构造：依次把 i 的出现位置从大到小列出。

这样可以依靠排列统计序列。这个排列每个上升位置意味着对应的序列值 +1。这样可以通过欧拉数统计答案。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=998244353,maxn=5e3+5;
int f[maxn][maxn],n,fac[maxn],ifac[maxn];
int qp(int a,int b){
    if(b==0)return 1;
    int T=qp(a,b>>1);T=T*T%mod;
    if(b&1)return T*a%mod;
    return T;
}
signed main(){
    cin>>n;
    fac[0]=1;
    for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%mod;
    ifac[n]=qp(fac[n],mod-2);
    for(int i=n-1;i>=0;i--)ifac[i]=ifac[i+1]*(i+1)%mod;
    f[0][0]=1;
    for(int i=1;i<=n;i++){
        f[i][0]=1;
        for(int j=1;j<=i;j++){
            f[i][j]=(f[i-1][j]*(j+1)%mod+f[i-1][j-1]*(i-j)%mod)%mod;
        }
    }
    for(int i=0;i<n;i++){
        int res=0;
        for(int j=1;j<=n;j++){
            (res+=ifac[j]*f[j][i])%=mod;
        }
        cout<<res*fac[n]%mod<<" ";
    }
    cout<<endl;
    return 0;
}