E. Number of k-good subarrays

題意

定義 $bit(x)$ 為 $x$ 的二進制表示下 $1$ 的數量
一個數組的子段被稱為 $k?good$ 的當且僅當：對于這個子段內的每個數 $x$，都有 $bit(x)\le k$

現在給定一個長度為 $n$ 的數組 $a$，且 $?0\le i<n,a_i=i$，即 a = { 0 , 1 , 2 , . . . n ? 1 } a = \{0, 1, 2, ... n - 1\} a={0,1,2,...n?1}

求出 $a$ 中 $k?good$ 的子段數量

思路

首先我們觀察發現：可以先將原數組選出連續的若干段，使得每一段都是極大的 $k?good$ 子段，也就是不能再往兩邊擴了。假設這一段的長度為 $len$，那么這一段對答案的貢獻是：$C_{len+1}^2$

由于問題規模過大，我們考慮分治：
定義 $f(n,k)$ 為在 $[0,n?1]$ 中的 $k?good$ 子段數量，這個子狀態返回一個元組 { r e s , l , r } \{res, l, r\} {res,l,r}

• $res$ 表示 $[0,n?1]$ 里符合條件的子段數量
• $l$ 表示從頭開始的最長連續 $k?good$ 長度
• $r$ 表示從尾開始的最長連續 $k?good$ 長度

我們再找到一個最大的 $m$，使得 $2^m<n$，即 $2^m\le n?1$
并將 $[0,n?1]$ 分成兩段：$[0,2^m?1]$ 和 $[2^m,n?1]$
我們發現第一段其實就是子問題 $f(2^m,k)$，那么第二段呢？它并不從零開始，好像無法轉換成某一個子狀態。

__builtin_clzll ( n ) 可以算出 $n$ 的前導 $0$ 數量

其實 $2^m$ 的最高位一定是和 $n?1$ 的最高位相同的，那么我們就等價于提前為第 $m$ 為預定了一個 $1$，第二段就轉換成了子狀態：$f(n?2^m,k?1)$

因此，$f(n,k)=f(2^m,k)+f(n?2^m,k?1)$

不難發現，第二部分的復雜度為 $O(\log n)$，而第一部分由于它的第一個分量永遠為 $2$ 的整數次冪，因此第一部分最多有 $O(k?\log n)$ 種狀態，我們可以使用記憶化加速搜索

當我們得到兩個部分的返回 { r e s 1 , l 1 , r 1 } \{res_1, l_1, r_1 \} {res1?,l1?,r1?} 和 { r e s 2 , l 2 , r 2 } \{res_2, l_2, r_2 \} {res2?,l2?,r2?} 之后，我們可以歸并答案，由于之前我們把 $r_1$ 向前延伸和 $l_2$ 向后延伸的算在了 $re{s}_1$ 和 $re{s}_2$ 里，因此我們在合并中間的連續段的時候（合二為一），需要減掉之前的錯誤統計。

即 $res=re{s}_1+re{s}_2?C_{r_1+1}^2?C_{l_2+1}^2+C_{r_1+l_2+1}^2$

#include<bits/stdc++.h>
#define fore(i,l,r)	for(int i=(int)(l);i<(int)(r);++i)
#define fi first
#define se second
#define endl '\n'
#define ull unsigned long long
#define ALL(v) v.begin(), v.end()
#define Debug(x, ed) std::cerr << #x << " = " << x << ed;const int INF=0x3f3f3f3f;
const long long INFLL=1e18;typedef long long ll;template<class T>
constexpr T power(T a, ll b){T res = 1;while(b){if(b&1) res = res * a;a = a * a;b >>= 1;}return res;
}constexpr ll mul(ll a,ll b,ll mod){ //快速乘，避免兩個long long相乘取模溢出ll res = a * b - ll(1.L * a * b / mod) * mod;res %= mod;if(res < 0) res += mod; //誤差return res;
}template<ll P>
struct MLL{ll x;constexpr MLL() = default;constexpr MLL(ll x) : x(norm(x % getMod())) {}static ll Mod;constexpr static ll getMod(){if(P > 0) return P;return Mod;}constexpr static void setMod(int _Mod){Mod = _Mod;}constexpr ll norm(ll x) const{if(x < 0){x += getMod();}if(x >= getMod()){x -= getMod();}return x;}constexpr ll val() const{return x;}explicit constexpr operator ll() const{ return x; //將結構體顯示轉換為ll類型： ll res = static_cast<ll>(OBJ)}constexpr MLL operator -() const{ //負號，等價于加上ModMLL res;res.x = norm(getMod() - x);return res;}constexpr MLL inv() const{assert(x != 0);return power(*this, getMod() - 2); //用費馬小定理求逆}constexpr MLL& operator *= (MLL rhs) & { //& 表示“this”指針不能指向一個臨時對象或const對象x = mul(x, rhs.x, getMod()); //該函數只能被一個左值調用return *this;}constexpr MLL& operator += (MLL rhs) & {x = norm(x + rhs.x);return *this;}constexpr MLL& operator -= (MLL rhs) & {x = norm(x - rhs.x);return *this;}constexpr MLL& operator /= (MLL rhs) & {return *this *= rhs.inv();}friend constexpr MLL operator * (MLL lhs, MLL rhs){MLL res = lhs;res *= rhs;return res;}friend constexpr MLL operator + (MLL lhs, MLL rhs){MLL res = lhs;res += rhs;return res;}friend constexpr MLL operator - (MLL lhs, MLL rhs){MLL res = lhs;res -= rhs;return res;}friend constexpr MLL operator / (MLL lhs, MLL rhs){MLL res = lhs;res /= rhs;return res;}friend constexpr std::istream& operator >> (std::istream& is, MLL& a){ll v;is >> v;a = MLL(v);return is;}friend constexpr std::ostream& operator << (std::ostream& os, MLL& a){return os << a.val();}friend constexpr bool operator == (MLL lhs, MLL rhs){return lhs.val() == rhs.val();}friend constexpr bool operator != (MLL lhs, MLL rhs){return lhs.val() != rhs.val();}
};const ll mod = 1e9 + 7;
using Z = MLL<mod>;const ll INV = 500000004ll; //2的逆元std::map<std::pair<ll, int>, std::tuple<Z, ll, ll>> mem; //記憶化std::tuple<Z, ll, ll> dfs(ll n, int k){if(k < 0)   return {0, 0, 0};if(n == 1)  return {1, 1, 1}; //小于1只有0int m = 63 - __builtin_clzll(n);ll mid = 1ll << m;if(mid == n){--m;mid >>= 1;if(mem.count({n, k})) return mem[{n, k}];}auto [res1, l1, r1] = dfs(mid, k);auto [res2, l2, r2] = dfs(n - mid, k - 1);Z w1 = Z(r1) * (r1 + 1) * INV;Z w2 = Z(l2) * (l2 + 1) * INV;Z tmp(r1 + l2);Z res = res1 + res2 - w1 - w2 + tmp * (tmp + 1) * INV;ll l = l1, r = r2;if(l1 == mid) l += l2;if(r2 == n - mid)   r += r1;if((mid << 1) == n) mem[{n, k}] = {res, l, r};return {res, l, r};
}int main(){std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);int t;std::cin >> t;while(t--){ll n;int k;std::cin >> n >> k;auto [ans, l, r] = dfs(n, k);std::cout << ans << endl;}return 0;
}