题意

称在二进制下 0101 交替且最高位和最低位都是 11 的数为斑马数，如 (1)2=1,(10101)2=21(1)_2=1,(10101)_2=21。

对一个数 nn 来说，定义它的价值为最小的正整数 pp，使得 nn 能表示成 pp 个斑马数（可以相同也可以不同）。

求 [l,r][l,r] 中价值为 kk 的数个数。

l,r,k≤1018l,r,k\le 10^{18}。

题解

考虑一个数的最优分解，即分解成最少个斑马数之和。
设第 ii 个斑马数为 ziz_i，即 z1=1,z4=85z_1=1,z_4=85，分解中第 ii 个斑马数的次数为 cic_i。

假设某一个数的最优分解中含有了某个斑马数 zi(i>1)z_i(i>1) 至少 55 次以上，那么可以发现 5zi=zi+1+4zi−15z_i = z_{i+1} + 4z_{i-1}，不会使答案变劣。
若含有了 11 至少 55 次以上，用 z2=5z_2=5 替换掉会更优。

所以我们得出了第一个结论：每个数都存在一种最优分解，使得 ∀i,ci≤4\forall i, c_i\le 4。

若 ci=4c_i=4，且存在 j<ij<i，使 cj>0c_j>0，则有等式

{4zi+zj=zi+1+4zj−1 (j>1)4zi+z1=zi+1 (j=1)\begin{cases} 4z_i+z_j =z_{i+1} + 4z_{j-1}\ &(j>1)\\ 4z_i+z_1 =z_{i+1}\ &(j=1)\\ \end{cases}

哪一种情况都不会使答案变劣，所以得出第二个结论：每个数都存在一种最优分解，使得 cic_i 为一段前缀 00（可以没有），一个 44（可以没有），若干个 0∼30\sim 3 的数字。用正则表示就是 0*4?[0-3]*。

接下来我们考虑处理这样的一个问题：每个 ziz_i 都只能使用 0∼30\sim 3 次，总共使用了 kk 个数，得到的和中，有多少在 [1,n][1,n] 中。（可以发现这种数没有重复的表示方法）
把 nn 看作一种 5∗5* 进制数，第 ii 位的值代表 ziz_i 的次数，贪心从高往低去取，可以发现 nn 的每一位都小于等于 44。
问题就转化成了，在 5∗5* 进制小于等于 nn 的表示，每一位只能取 0∼30\sim 3，数位和为 kk 的数有多少个。

证明：

  1. 证明所有 5∗5* 进制下每一位只能取 0∼30\sim 3，以 55 进制比较，比 nn 小的数实际都比 nn 小：这是因为有一位比 nn 小，而 3∑j=1i−1zj<zi3\displaystyle\sum_{j=1}^{i-1}z_j < z_i，所以成立。
  2. 证明所有 5∗5* 进制下每一位只能取 0∼30\sim 3，以 55 进制比较，比 nn 大的数实际都比 nn 大：这是因为有一位比 nn 大，而 zi>3∑j=1i−1zjz_i > 3\displaystyle\sum_{j=1}^{i-1}z_j，所以也成立。

因此看作一个真正的 55 进制数位 dp 就能解决的。

回到原问题，首先可以前缀和，只需要解决 [1,n][1,n] 中的问题就可以了。
由上文的结论二我们知道，我们可以枚举这个数中唯一的 44 的位置，然后问题转化为：在 55 进制小于等于 nn 的表示，每一位只能取 0∼30\sim 3，有一段前缀强制是 00，数位和为 kk 的数有多少个，这也可以数位 dp 轻易完成。

还需要注意，这道题虽然 k≤1018k\le 10^{18}，但由结论我们不难看出 k∼O(log⁡n)k\sim O(\log n)，所以设一个上限即可，超过上限直接输出 00。（取 9090 比较好）

总复杂度 O(log⁡2n)O(\log^2 n)。

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
vector<ll> p;

const int MAX_CNT = 100;
const int LEN = 31;

ll mem[LEN][LEN][MAX_CNT+1];
int num[LEN];
ll dfs(int u,int end,int cnt,bool lim){
    if(u==end)return cnt==0;
    if(!lim && ~mem[u][end][cnt])return mem[u][end][cnt];
    ll ans = 0;
    int L = 0, R = lim?num[u]:3;
    for(int i=L;i<=min(R,3);i++){
        if(i>cnt)break;
        ans += dfs(u-1,end,cnt-i,lim&&i==R);
    }
    if(!lim)mem[u][end][cnt]=ans;
    return ans;
}

ll precalc(ll n,ll end,ll cnt){
    if(cnt>MAX_CNT)return 0;
    for(int i=p.size()-1;i>=0;i--){
        num[i+1]=0;
        while(n>=p[i]){
            n-=p[i], num[i+1]++;
        }
    }
    return dfs(p.size(),end,cnt,1);
}

ll calc(ll n,ll k){
    ll ans = 0;
    ans += precalc(n,0,k);
    if(k<4)return ans;
    for(int i=0;i<p.size();i++){
        if(p[i]*4 <= n) ans+=precalc(n-p[i]*4, i+1, k-4); 
    }
    return ans;
}

void solve(){
    ll l,r,k; cin>>l>>r>>k;
    cout << calc(r,k) - calc(l-1,k) << '\n';
}

int main(){
    memset(mem,-1,sizeof(mem));

    ios::sync_with_stdio(0);cin.tie(0);

    p.push_back(1);
    while(p.back()*4+1 <= 1e18)p.push_back(p.back()*4+1);

    int T; cin>>T;
    while(T--)solve();
    return 0;
}