设 \(f_{i,j}\) 表示前 \(i\) 个位置使用 \(j\) 个 \(1\) 的方案数。
转移很简单：\(f_{i,j}=f_{i-1,j}+f_{i-1,j-1}\)
但是有些状态是非法的，所以对于每个 \(i\) 求出其前缀可以操作的最右的位置 \(R_i\)，以及 \(pre_i\) 表示前缀 \(1\) 的数量。
于是 \(1\) 的数量 \(\in[\max(0,i-(R_i-pre_{R_i})),\min(i,pre_{R_i})]\)。
时间复杂度 \(\mathcal O(n^2)\)。
Code：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3005, mod = 1e9 + 7;
int n, m;
char s[N];
int pre[N], R[N];
int f[N][N];
void add(int &a, int b) {
a += b;
if (a >= mod) a -= mod;
}
int main() {
scanf("%d%d%s", &n, &m, s + 1);
for (int i = 1; i <= n; ++i) pre[i] = pre[i - 1] + (s[i] - '0'), R[i] = i;
for (int i = 1, l, r; i <= m; ++i) scanf("%d%d", &l, &r), R[l] = max(R[l], r);
for (int i = 1; i <= n; ++i) R[i] = max(R[i], R[i - 1]);
f[0][0] = 1;
for (int i = 1; i <= n; ++i) {
int mx = min(i, pre[R[i]]), mn = max(0, i - (R[i] - pre[R[i]]));
for (int j = mn; j <= mx; ++j) {
add(f[i][j], f[i - 1][j]);
if (j) add(f[i][j], f[i - 1][j - 1]);
}
}
printf("%d", f[n][pre[n]]);
return 0;
}