提示1: +lowbit 和 +highbit 两种运算的作用相互抵消。

考虑变化中 \(x\) 的二进制，思考为什么成立。

提示2:在\([2^i, 2^{i+1})\)的数中，设操作区间中 +lowbit 的次数比 +highbit 的次数多 \(t\) 次(*)，对于 \(t=0,1,...\) 有多少个数可以变为 \(2^a\) 的形式？可以写暴力程序打表找规律，也可以数学推导。

这里建议打表，很快可以发现规律。

提示3:本题的优化。

①想知道操作序列中取一个长度不超过 \(k\) 的连续子列，\(1\) 的个数与 \(0\) 的个数的差值的最大值。可以采用前缀和+单调队列(滑动窗口) 优化。

②打表的结果应该类似于杨辉三角
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
...
杨辉三角每一列的前缀和有通项公式，所以答案可以按每一列计算，再加起来。

总的时间复杂度 \(O(d)\) ，（不采取这两个优化，时间复杂度是\(O(k(n+d))\))

Code:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9+7;
ll powmod(ll a, ll b){ ll res = 1;a %= mod; assert(b >= 0); for (; b; b >>= 1) { if (b & 1) res = res * a % mod; a = a * a % mod; } return res; }
ll inv(ll x) { return powmod(x, mod - 2); }
ll cal(ll t, ll x)
{
    ll q = x, now = x, res = x;
    for(int i=1;i<=t;i++) 
    {
        now = now * (--q) % mod * inv(i+1) % mod;
        res = (res + now) % mod;
    }
    return res;
}

class Mqueue{
    struct node{
        int index;
        int val;
    };
    int k, now = 0, min = false; // true: 最大值
    deque<node> q;
public:
    Mqueue(int a, bool b = false): k(a), min(b){}
    void push(int x)
    {
        now++;
        while(!q.empty()&&q.front().index+k<=now) q.pop_front();
        if(!min) while(!q.empty()&&q.back().val<=x) q.pop_back();
        else while(!q.empty()&&q.back().val>=x) q.pop_back();
        q.push_back((node){now,x});
    }
    int getval(){return q.front().val;}
};

int main()
{
    ll m, n, k, d; cin>>m>>n>>k>>d;
    string s; cin>>s;
    int a[d+1] = {0};
    for(int i=1;i<=d;i++) a[i] = (s[i-1] == '1' ? -1 : 1);
    for(int i=2;i<=d;i++) a[i] += a[i-1];
    Mqueue Q(k, true);
    
    int l = 0;
    for(int i=1;i<=d;i++) 
    {
        l = max(l, a[i] - Q.getval());
        Q.push(a[i]);
    }
    cout <<(1 + cal(l, n) - cal(l, m) + mod) % mod;
    return 0;
}

(*)严格来说，这里应该表述为，操作区间[l,r]的所有前缀[l,x]中，+lowbit的次数比+highbit的次数至多多 \(t\) 次。