观察数据

题面中给出了一组示例的「无限序列」：1011010110110101101011011010110110

依照题面的意义构造出前几列数据如下。

1
10
101
10110
10110101
1011010110110

不难看出，第 \(N\) 项是由第 \(N-1\) 项后拼接第 \(N-2\) 项得到的。

即可以将 1011010110110 分解如下。

10110101 10110
10110 101 101 10
101 10 10 1 10 10
10 1 10 10 1 10 10

即分解成若干个由 10 与 1 组成的串，由此，联想到递归，尝试递归解题。

分析递归

我们刚才观察了数据的结构，现在来尝试递归解题。

首先我们尝试对于 1 5 这一组数据进行分析，我们尝试构思一个函数 cal() ，向其中传入一个数字 \(N\) 后，它就会给出从 \(1\to{N} \) 包括 \(N\) 的 1 的数量。所以得到代码如下。

...
int main() {
    int T;
    ...
    while (...) {
       ...
       cin >> a >> b;
       cout << cal(b) - cal(a - 1); // 注意取值范围
    }
}

接下来构造递归函数，可以预见的是，我们可以用 map 这类储存方法来加速。

const unsigned long long num[1000] = {0, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144... // 兔子数列
map<unsigned long long, unsigned long long> reflex;
unsigned long long cal(unsigned long long pos) {
    if (pos == 0) {
        ...
    if (pos == 1)
        ...
    if (pos == 2)
        ...
    if (reflex.count(...))
        ...
    int ...;
    while (...) ; // 这里需要注意一下
    ...
    reflex[pos] = cal(num[...]) + cal(pos - num[...]);
    return reflex[pos];
}

代码

#include <bits/stdc++.h>
using namespace std;
#define fslkj const
#define fflgkk if
#define minus ==
#define forr while

fslkj unsigned long long num[1000] = {0, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976, 7778742049, 12586269025, 20365011074, 32951280099, 53316291173, 86267571272, 139583862445, 225851433717, 365435296162, 591286729879, 956722026041, 1548008755920, 2504730781961, 4052739537881, 6557470319842, 10610209857723, 17167680177565, 27777890035288, 44945570212853, 72723460248141, 117669030460994, 190392490709135, 308061521170129, 498454011879264, 806515533049393, 1304969544928657, 2111485077978050, 3416454622906707, 5527939700884757, 8944394323791464, 14472334024676221, 23416728348467685, 37889062373143906, 61305790721611591, 99194853094755497, 160500643816367088, 259695496911122585, 420196140727489673, 679891637638612258, 1100087778366101931, 1779979416004714189};
map<unsigned long long, unsigned long long> __bsfdjklj2;
fslkj int xi = 34;
unsigned long long cal(unsigned long long __asdlffa0gojv) {
//  cout << __asdlffa0gojv << endl;
    fflgkk (__asdlffa0gojv minus 0) {
        return 0;
    }
    fflgkk (__asdlffa0gojv minus 1) {
        return 1;

    }
    fflgkk (__asdlffa0gojv minus 2)
        return 1;
    fflgkk (__bsfdjklj2.count(__asdlffa0gojv)) {
        return __bsfdjklj2[__asdlffa0gojv];
    }
    int p = 0;
    forr (num[++p] < __asdlffa0gojv) ;
    --p;
    __bsfdjklj2[__asdlffa0gojv] = cal(num[p]) + cal(__asdlffa0gojv - num[p]);
//  cout << __bsfdjklj2[__asdlffa0gojv];
    return __bsfdjklj2[__asdlffa0gojv];
}

signed main() {
    int __t134435234;
    cin >> __t134435234;
    forr(__t134435234--) {
        unsigned long long a, b;
        cin >> a >> b;
        cout << cal(b) - cal(a - 1) << "\n";
    }
    return 0;
}

请注意，这个代码可能并不能正常通过此题，仅为示例。