题解：P14568 【MX-S12-T3】排列

· · 题解

截至目前的最短解。

考虑从 1 到 n 依次确定每个数在 [1,i] 中的相对大小，那么每次可以在前 i-1 个数中的任意位置插入 a_i。

如果 op_i=\{0,1\}，那么我们确定 i 在前 i 个数中的是最大 / 最小的。

如果 op_i=\{2,3\}，那么我们限制相当于以后的数比现在大 / 小。

记录一下当前剩下的空位个数即可。

设 f_{i,j} 表示考虑到前 i 个数，当前有 j+1 个空位的方案数，那么有转移：

f_{i,j}=f_{i-1,j-1},op_i=\{0,1\} f_{i,j}=\sum_{k\ge j} f_{i-1,k},op_i=\{2,3\}

复杂度 O(n^2)。

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int n,flag,a[5005],f[5005][5005],ans;
void add(int &a,int b){
    a+=b;
    a=(a>=mod?a-mod:a);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0); 
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            if(a[i]==3 && a[j]==1) flag=true;
            if(a[i]==2 && a[j]==0) flag=true;
        }
    }
    if(flag){
        cout<<0;
        return 0;
    }
    f[0][0]=1;
    for(int i=1;i<=n;i++){
        if(a[i]==0 || a[i]==1) for(int j=1;j<=n;j++) add(f[i][j],f[i-1][j-1]);
        else for(int j=n;j>=0;j--) add(f[i][j],f[i][j+1]),add(f[i][j],f[i-1][j]);
    }
    for(int i=0;i<=n;i++) add(ans,f[n][i]);
    cout<<ans;
    return 0;
}