P14568 【MX-S12-T3】排列
前言
本题解思路来自梦熊直播视频讲解，本文将进行完整的讲解且给出代码。
思路
对于由 \(op_i=\{0,1\}\) 和 \(op_i=\{2,3\}\) 构成的两个序列，他们内部之间的相对关系是确定的，可以将两个序列根据相对大小来从小到大提取出来分别为序列 \(a\) 和序列 \(b\)。
接下来将序列的每个数赋值，对于数字 \(1\)，能且仅能赋给 \(a_1\) 和 \(b_1\)，接下来数字 \(2\)，可以赋给 \(a_2\) 或 \(b_1\) 及另一种情况 \(a_1\) 或 \(b_2\)，以此类推。可以设 dp 状态为 \(f_{i,j}\) 表示 \(a\) 序列中已赋值了前 \(i\) 个数，\(b\) 序列中已赋值了前 \(j\) 个数的方案数。
大部分的转移方程为：
\[f_{i+1,j}=f_{i+1,j}+f_{i,j}
\\
f_{i,j+1}=f_{i,j+1}+f_{i,j}
\]
但有不合法情况时不能转移，因为我们是从小到大填数，当填的下一个数为前缀最小值时，如果在这个位置左边已填过后缀最大值时，这个位置就没法填。同理当我们填下一个后缀最小值时，看右边是否填过一个前缀最大值。
当然判断是否合法可以预处理，\(prea_i\) 为填了前 \(i\) 个 \(a_j\) 且 \(op_j=1\) 中最右的位置，\(preb_i\) 为填了前 \(i\) 个 \(b_j\) 且 \(op_j=3\) 中最左的位置。
部分应判断是否合法的转移方程为：
\[f_{i+1,j}=f_{i+1,j}+f_{i,j},preb_j>a_{i+1},op_{a_{i+1}}=0
\\
f_{i,j+1}=f_{i,j+1}+f_{i,j},prea_i<b_{j+1},op_{b_{j+1}}=2
\]
代码
#include<bits/stdc++.h>
#define ll long long
#define int ll
using namespace std;
const int N=1e6+10;
const int mod=998244353;
const int INF=1e18+7;int n;
deque<int> q;
deque<int> p;int a[N];
int b[N];
int c[N];int f[5005][5005];int preb[N];
int prea[N];void solve(){cin>>n;for(int i=1;i<=n;i++){cin>>c[i];if(c[i]==0){q.push_front(i);//小的放前 }else if(c[i]==1){q.push_back(i);//大的放右 }}for(int i=n;i>=1;i--){//倒着枚举 if(c[i]==2){p.push_front(i);//小的放左 }else if(c[i]==3){p.push_back(i);//大的放右 }}//判断是否存在不可能赋值的情况 int op=0;for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){if(c[i]==3&&c[j]==1){op=1;}if(c[i]==2&&c[j]==0){op=1;}}}if(op){cout<<0;return;}//构建a,b序列（储存位置下标） int lena=0,lenb=0;while(!q.empty()){a[++lena]=q.front();q.pop_front();}while(!p.empty()){b[++lenb]=p.front();p.pop_front();}//预处理 prea[0]=0;for(int i=1;i<=lena;i++){prea[i]=prea[i-1];if(c[a[i]]==1){//前缀最大值 prea[i]=max(prea[i-1],a[i]);//最靠右的位置 }}preb[0]=INF;for(int i=1;i<=lenb;i++){preb[i]=preb[i-1];if(c[b[i]]==3){//后缀最大值 preb[i]=min(preb[i-1],b[i]);//最靠左的位置 }}f[0][0]=1;for(int i=0;i<=lena;i++){for(int j=0;j<=lenb;j++){if(c[a[i+1]]==1||preb[j]>a[i+1]){//最小前缀前有最大的后缀 f[i+1][j]+=f[i][j];f[i+1][j]%=mod;}if(c[b[j+1]]==3||prea[i]<b[j+1]){//最小后缀后有最大的前缀f[i][j+1]+=f[i][j];f[i][j+1]%=mod;}}} cout<<f[lena][lenb];
}signed main(){ios::sync_with_stdio(0);cin.tie(nullptr); solve();return 0;
}