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

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

设 fi 表示 [1,i] 的划分方案数，有 fi=∑0≤j<i[|(sum0,i−sum0,j)−(sum1,i−sum1,j)|≤k]fj。

|(sum0,i−sum0,j)−(sum1,i−sum1,j)|≤k−k≤(sum0,i−sum0,j)−(sum1,i−sum1,j)≤k⇓sum0,i−sum0,j≤sum1,i−sum1,j+ksum0,i−sum0,j≥sum1,i−sum1,j−k⇓sum0,i−sum1,i−k≤sum0,j−sum1,jsum0,i−sum1,i+k≥sum0,j−sum1,j

然后这个条件就变成了二维偏序，用树状数组按照 sum0,i−sum1,i 来维护即可。
注意要整体移动 n 位，避免负数。

代码：

#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]);
}