[ARC127E] Priority Queue

有一种显然的想法：我们要考虑对每段操作中保留下来的数。但是这并不好做。
正难则反：我们只需要关注删除掉的数。
那么我们就需要得知删除每个数时的限制，这等价于求每个删除操作之前保留了多少数。
具体地，记 \(f_{i,j}\) 表示删除第 \(i\) 个数，前 \(i\) 个数共删除了 \(j\) 个的方案数。那么我们能在第 \(j\) 次删除 \(i\) 的条件就是第 \(j\) 次删除操作前保留了最多 \(i - j\) 个数。只要满足限制即可转移。

#include<bits/stdc++.h>
#define RG register
#define LL long long
#define U(x, y, z) for(RG int x = y; x <= z; ++x)
#define D(x, y, z) for(RG int x = y; x >= z; --x)
#define update(x, y) (x = x + y >= mod ? x + y - mod : x + y)
using namespace std;
void read(){}
template<typename _Tp, typename... _Tps>
void read(_Tp &x, _Tps &...Ar) {
	x = 0; char ch = getchar(); bool flg = 0;
	for (; !isdigit(ch); ch = getchar()) flg |= (ch == '-');
	for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
	if (flg) x = -x;
	read(Ar...);	
}
inline char Getchar(){ char ch; for (ch = getchar(); !isalpha(ch); ch = getchar()); return ch;}
template <typename T> inline void write(T n){ char ch[60]; bool f = 1; int cnt = 0; if (n < 0) f = 0, n = -n; do{ch[++cnt] = char(n % 10 + 48); n /= 10; }while(n); if (f == 0) putchar('-'); for (; cnt; cnt--) putchar(ch[cnt]);}
template <typename T> inline void writeln(T n){write(n); putchar('\n');}
template <typename T> inline void writesp(T n){write(n); putchar(' ');}
template <typename T> inline void chkmin(T &x, T y){x = x < y ? x : y;}
template <typename T> inline void chkmax(T &x, T y){x = x > y ? x : y;}
template <typename T> inline T Min(T x, T y){return x < y ? x : y;}
template <typename T> inline T Max(T x, T y){return x > y ? x : y;}
inline void readstr(string &s) { s = ""; static char c = getchar(); while (isspace(c)) c = getchar(); while (!isspace(c)) s = s + c, c = getchar();}
inline void FO(string s){freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout);}

const int N = 5e3 + 10, mod = 998244353;
int n, m, u[N], v[N], top, a[N], f[N][N], s[N][N];

int main(){
	//FO("");
	read(n, m);
	U(i, 1, n + m) {
		int x;
		read(x);
		if (x == 1) u[++top] = 1, v[top] = 0;
		else {
			v[top]++;
			while (u[top] < v[top]) 
				u[top - 1] += u[top], v[top - 1] += v[top], --top;
		}
	}

	m = 0;
	int sz = 0;
	U(i, 1, top) {
		sz += u[i] - v[i];
		U(j, 1, v[i])
			a[++m] = sz;
	}

	f[0][0] = s[0][0] = 1;
	U(i, 1, n) { 
		U(j, 1, i) {
			if (a[j] <= i - j) f[i][j] = s[i - 1][j - 1];
			(s[i][j] = s[i - 1][j] + f[i][j]) %= mod;

		}
		s[i][0] = 1;
	}
	int ans = 0;
	U(i, 0, n) update(ans, f[i][m]);
	writeln(ans);
	return 0;
}