JZOJ 4738.神在夏至祭降下了神谕

看这题名字挺优美就去做了,结果一眼秒掉(虽然写错了一次)……

fif_i 表示 [1,i][1,i] 的划分方案数,有 fi=0j<i[(sum0,isum0,j)(sum1,isum1,j)k]fjf_i = \sum\limits_{0\le j<i} [|(sum_{0,i} - sum_{0,j}) - (sum_{1,i} - sum_{1,j})|\le k] f_j

然后这个条件就变成了二维偏序,用树状数组按照 sum0,isum1,isum_{0,i} - sum_{1,i} 来维护即可。
注意要整体移动 nn 位,避免负数。

代码:

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
#include <cstdio>
#include <algorithm>
#define lowbit(x) ((x) & -(x))
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]);
}