看这题名字挺优美就去做了，结果一眼秒掉（虽然写错了一次）……
设 \(f_i\) 表示 \([1,i]\) 的划分方案数，有 \(f_i = \sum\limits_{0\le j<i} [|(sum_{0,i} - sum_{0,j}) - (sum_{1,i} - sum_{1,j})|\le k] f_j\)。
\[\begin{align*} |(sum_{0,i} - sum_{0,j}) - (sum_{1,i} - sum_{1,j})| & \le k \\ -k \le (sum_{0,i} - sum_{0,j}) & - (sum_{1,i} - sum_{1,j}) \le k \\ & \Downarrow \\ sum_{0,i} - sum_{0,j} & \le sum_{1,i} - sum_{1,j} + k \\ sum_{0,i} - sum_{0,j} & \ge sum_{1,i} - sum_{1,j} - k \\ & \Downarrow \\ sum_{0,i} - sum_{1,i} - k & \le sum_{0,j} - sum_{1,j} \\ sum_{0,i} - sum_{1,i} + k & \ge sum_{0,j} - sum_{1,j} \\ \end{align*}\]
然后这个条件就变成了二维偏序，用树状数组按照 \(sum_{0,i} - sum_{1,i}\) 来维护即可。
注意要整体移动 \(n\) 位，避免负数。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
using namespace std;
const int N = 1e5;
const long long mod = 1e9 + 7;
int n,k,sum[2][N + 5];
long long f[N + 5],c[(N << 1) + 5];
inline void update(int x,long long k)
{
x += n + 1;
for(;x <= 2 * n + 1;x += lowbit(x))
c[x] = (c[x] + k) % mod;
}
inline long long query(int x)
{
x += n + 1;
long long ret = 0;
for(;x;x -= lowbit(x))
ret = (ret + c[x]) % mod;
return ret;
}
int main()
{
scanf("%d%d",&n,&k);
int x;
for(register int i = 1;i <= n;++i)
scanf("%d",&x),sum[0][i] = sum[0][i - 1] + !x,sum[1][i] = sum[1][i - 1] + x;
update(0,f[0] = 1);
for(register int i = 1;i <= n;++i)
update(sum[0][i] - sum[1][i],f[i] = (query(min(sum[0][i] - sum[1][i] + k,n)) - query(max(sum[0][i] - sum[1][i] - k - 1,-n)) + mod) % mod);
printf("%lld\n",f[n]);
}