队列排序
有队列 $A,B$，现在使用这两个队列对长度为 $n$ 的序列 $b$ 排序，具体地：
- 按照 $b_1 \sim b_n$ 的顺序枚举 $b_i$，将 $b_i$ 放入队列 $A$ 或队列 $B$ 的队尾。
- 当队列 $A,B$ 中有至少一个队列非空时，弹出序列 $A$ 的队首或队列 $B$ 的队首，将其添加至序列 $c$ 的尾部。
如果存在某种操作顺序能够使得序列 $c$ 是一个单调不降序列，就认为可以对序列 $b$ 完成队列排序。
给定一些数字，求这些数字组成的序列中有多少种序列可以完成序列排序，两个序列不同当且仅当存在一个位置上的数字不同，答案对 $998244353$ 取模。
输入一个正整数 $m$ 表示给定数字的值域，接下来输入 $a_1 \sim a_m$，其中 $a_i$ 表示数字 $i$ 的数量。
$1 \leq m \leq 500$，$0 \leq a_i \leq m$，$\sum_{i=1}^{m} a_i \leq 500$。
贪心、动态规划、Dilworth 定理
在完成入队步骤后，队列 $A,B$ 内部的数字必须有序才能通过归并得到有序序列，因此一个序列能够完成队列排序当且仅当其能被划分为不超过 $2$ 个单调不降子序列。
根据 Dilworth 定理，一个序列能够完成队列排序当且仅当序列的最长下降子序列长度不超过 $2$。问题转化为计算能够得到的最长下降子序列长度不超过 $2$ 的序列数量。
考虑按照值域从小到大向序列中插入数字，每次插入所有值为 $i$ 的数字（可能有多个）。
设计 $dp_{i,j}$ 为考虑了 $1 \sim i$ 的值，并且第一个数下标最大的长度为 $2$ 的最长下降子序列的第一个数下标为 $j$ 的方案数。对于状态为 $dp_{i,j}$ 的序列，插入更大的数时，这些新的数只能插在位置 $j$ 的后面，否则会形成一个长度为 $3$ 的下降子序列。
特殊地，设计 $dp_{i,0}$ 为不存在长度为 $2$ 的下降子序列的序列数量，显然 $dp_{i,0}$ 恒等于 $1$。
考虑从 $dp_{i-1}$ 向 $dp_i$ 的转移，枚举插入的下标最大并且后面还有小于 $i$ 的数的位置 $k$ 进行转移（插入到状态 $dp_{i-1}$ 对应的序列中位置 $k$ 的前面，也就是说 $k$ 不超过 $1 \sim i-1$ 的出现次数之和）。
这样做信息不够，还需要再加一重循环枚举在放在序列尾部的 $i$ 的数量，将这个数量记为 $q$，考虑 $dp_{i-1,j}$ 会怎么转移。单独处理把所有 $i$ 都插入序列尾部的情况。
当 $j < k$ 时才能转移，使用 $w_i$ 表示数字 $i$ 的数量，钦定在位置 $k$ 之前插一个 $i$，现在有 $w_i - q - 1$ 个 $i$ 可以随便插。此时有 $k - j$ 个空位可以放这些 $i$，由隔板法可知有 $C((w_i-q-1)+(k-j-1),k-j-1)$ 种插入方法。由于钦定插入在原序列位置 $k$ 之前的数前面还插了 $w_i - q -1$ 个数字，状态会从 $dp_{i-1,j}$ 转移到 $dp_{i,k+(w_i-q-1)}$。
这样转移要枚举 $j,k,q$ 三个变量，因为 $\sum q = \sum a_i$，时间复杂度 $O(n^3)$，可以通过。
#include<bits/stdc++.h>
using namespace std;
constexpr int mod=998'244'353;
long long dp[505][505],C[1'005][1'005];
int n,m,cnt,a[505];
void calculate(int x){
for(int i=0;i<=cnt;i++){//从 dp[x-1][i] 转移
for(int j=i+1;j<=cnt;j++){
for(int k=0;k<=a[x]-1;k++){
dp[x][j+a[x]-k-1]=(dp[x][j+a[x]-k-1]+dp[x-1][i]*C[a[x]-k-1+j-i-1][j-i-1])%mod;
}
}
//单独处理把全部 x 都插入序列尾部的情况
dp[x][i]=(dp[x][i]+dp[x-1][i])%mod;
}
cnt+=a[x];
}
int main(){
ios::sync_with_stdio(0);
static constexpr int lim=1'000;
C[0][0]=1ll;
for(int i=1;i<=lim;i++){
C[i][0]=1ll;
for(int j=1;j<=i;j++) C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
}
cin>>m;
for(int i=1;i<=m;i++){
static int x;
cin>>x;
if(x!=0) a[++n]=x;
}
dp[0][0]=1ll;
for(int i=1;i<=n;i++) calculate(i);
long long ans=0ll;
for(int i=0;i<=cnt;i++) ans=(ans+dp[n][i])%mod;
cout<<ans<<'\n';
return 0;
}