Description：

给一个 $01$ 序列，问有多少种划分方式使得每段 $0$ 和 $1$ 个数相差不超过 $k$ 。

$1\leqslant n\leqslant 10^5$

Solution：

设 $f[i]$ 表示划分前 $i$ 个的方案数，转移为： $$ f[i]=\sum_{j=1}^{i-1}f[j](|s_0[i,j]-s_1[i,j]|\leqslant k) $$ 直接做是 $O(n^2)$ 的，设 $d[i][j]=s_0[i,j]-s_1[i,j]$ ，发现每次往后一位，对于所有 $d[i][j]$ 都会增大或减小一，那么就可以不移动 $d[i][j]$ 而是移动原点，即每次 $+1$ 原点就相对减一，否则加一，每次把当前这个 $f$ 插入到原点位置即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;

	register char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

int n,k;

#define MAXN 100010

#define MOD 1000000007

int a[MAXN];

int c[MAXN * 3];

int lowbit(int x){return x & (-x);}

void add(int p,int x){for(int i = p;i <= n + MAXN * 2;i += lowbit(i))c[i] = (c[i] + x) % MOD;return;}

int query(int p){int res = 0;for(int i = p;i >= 1;i -= lowbit(i))res = (res + c[i]) % MOD;return res;}

int f[MAXN];

int main()

{

	scanf("%d%d",&n,&k);

	for(int i = 1;i <= n;++i)a[i] = rd();

	int cur = 0;

	add(cur + MAXN,1);

	for(int i = 1;i <= n;++i)

	{

		if(a[i] == 1)--cur;

		else ++cur;

		f[i] = (query(min(cur + k + MAXN,3 * MAXN)) - query(max(0,cur - k - 1 + MAXN)) + MOD) % MOD;

		add(cur + MAXN,f[i]);

	}

	cout << f[n] << endl;

	return 0;

}