题目描述
我们按以下方式产生序列：
- 开始时序列是：
1；- 每一次变化把序列中的
1变成10，0变成1。经过无限次变化，我们得到序列
1011010110110101101...。总共有$Q$个询问，每次询问为：在区间$a$和$b$之间有多少个
1。任务：写一个程序回答$Q$个询问。
输入格式
输入的第一行为一个整数 ，后面有$Q$行，每行两个数用空格隔开的整数$a,b$。
输出格式
输出共$Q$行，每行一个回答。
样例
样例输入
1
2 8样例输出
4
数据范围与提示
对于$100\%$的数据，$1\leq Q\leq 5000$，$1\leq a \leq b \leq 2^{63}$。
做的时候先是手推到了变换8次后的结果试图找出循环节但是我失败了（
然后发现了第$i$次变换后的序列的前一部分就是第$i-1$次变换的序列
然后就发现第$i$次变换后的序列的后一部分就是第$i-2$次变换的序列
但是没发现这好像可以继续拆下去然后发现了第$i$次变换后的序列中有个斐波那契数列第i项个1
然后甚至意识到了$[a,b]$区间内的1的数量等于$[1,b]$与$[1,a-1]$区间内的个数差
然后我就不会了。。。
看了一些题解，终于发现这个序列是可以不断拆分到10和1的
1
2
3
4
5
6
7
8
9
10
11
12
13//提前预处理出斐波那契数列1~99项的值
//f函数用于寻找第1~m之间1的个数
long long f(long long m){
if(m < 3) return n1[m];
//最好是从小往大找，因为这个序列是越拆越短的
for(int i = 3;i<=99;i++){
//如果长度正好等于预处理出的长度的第i项，那么1的个数也正好为对应的个数的第i项
if(le[i] == m) return n1[i];
//如果预处理出的长度第i项长于当前长度（即第一个长于长度的值），那么就接着拆后半部分
//拆完后得到的1的数量加上前半部分的1的数量即可
if(le[i] > m) return f(m-le[i-1]) + n1[i-1];
}
}
举个栗子
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下面是变换8次后的序列
1011 0101 1011 0101 1010 1101 1010 1101 10
n1 = [1,1,2,3,5,8 ,13,...]
le = [1,2,3,5,8,13,21,...]
求在[3,18]区间内的1的数量
先求[1,18]区间内的1的数量
[1011 0101 1011 0101 10]10 1101 1010 1101 10
最短的长于14的完整序列长度为21
那么就可知最长的短于14的完整序列长为13
即
[1011 0101 1011 0]101 1010 1101 1010 1101 10
因此[1,18]区间内的1的数量为[1,13]与[14,18]之间的1的数量和
通过查询可知，[1,13]区间内有8个1
接下来将[14,18]拆分为[14,17]与[17,18]这两个完整序列
即[14,18]间1的数量为以下两部分完整序列的和：
[14,17]这个长为3的完整序列中的1的数量
[17,18]这个长为2的完整序列中的1的数量
因此，[14,18]间的1的数量为2+1=3个
因此[1,18]区间内有8+3=11个1
同理可知[1,2]区间内有1个1
所以[3,18]间有11-1=10个1
还有就是
$\Huge{不开\text{long long}见祖宗}$