Problem Description
众所周知，度度熊喜欢的字符只有两个：B和D。
今天，它发明了一种用B和D组成字符串的规则：
S(1)=B
S(2)=BBD
S(3)=BBDBBDD
…
S(n)=S(n−1)+B+reverse(flip(S(n−1))
其中，reverse(s)指将字符串翻转，比如reverse(BBD)=DBB，flip(s)指将字符串中的B替换为D，D替换为B，比如flip(BBD)=DDB。
虽然度度熊平常只用它的电脑玩连连看，这丝毫不妨碍这台机器无与伦比的运算速度，目前它已经算出了S(21000)的内容，但度度熊毕竟只是只熊，一次读不完这么长的字符串。它现在想知道，这个字符串的第L位（从1开始）到第R位，含有的B的个数是多少？
今天，它发明了一种用B和D组成字符串的规则：
S(1)=B
S(2)=BBD
S(3)=BBDBBDD
…
S(n)=S(n−1)+B+reverse(flip(S(n−1))
其中，reverse(s)指将字符串翻转，比如reverse(BBD)=DBB，flip(s)指将字符串中的B替换为D，D替换为B，比如flip(BBD)=DDB。
虽然度度熊平常只用它的电脑玩连连看，这丝毫不妨碍这台机器无与伦比的运算速度，目前它已经算出了S(21000)的内容，但度度熊毕竟只是只熊，一次读不完这么长的字符串。它现在想知道，这个字符串的第L位（从1开始）到第R位，含有的B的个数是多少？
Input
第一行一个整数T，表示T(1≤T≤1000) 组数据。
每组数据包含两个数L和R(1≤L≤R≤1018) 。
每组数据包含两个数L和R(1≤L≤R≤1018) 。
Output
对于每组数据，输出S(21000)表示的字符串的第L位到第R位中B的个数。
Sample Input
3
1 3
1 7
4 8
1 3
1 7
4 8
Sample Output
2
4
3
4
3
Source
Recommend
思路：可以用一个函数calc（x），表示从第一位到第x位中B字符的个数，则结果为calc（R）-calc（L），怎么样求calc（x）呢？
用一个数组a[1]~a[60]（a[60]>10^18&a[59]<10^18）表示s(1)~s(60)的串长，若x==a[i],则sum=a[i]/2+1;若x<a[i]&x>a[i-1],则对应a[i-1]+1的字符一定为B，那么关于a[i-1]+1对称的两部分a[i-1]+2~x与a[i]-R+1~a[i-1]字符串取反后对称，所以这两部分字符转中B的个数和为R-a[i-1]-1,加上中间对称的B，个数为R-a[i-1],总的B字符个数为R-a[i-1]+calc(a[i]-R),然后递归求解calc（a[i]-R）;
代码如下：
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
long long a[];
long long calc(long long x)
{
if(x==) return ;
long long sum=;
for(int i=;i<=;i++)
{
if(a[i]==x)
return x/+;
if(x<a[i])
{
sum+=x-a[i-];
sum+=calc(a[i]-x);
break;
}
}
return sum;
}
int main()
{
int T;
long long L,R;
scanf("%d",&T);
a[]=;
for(int i=;i<=;i++)
{
a[i]=a[i-]*+;
}
while(T--)
{
scanf("%I64d%I64d",&L,&R);
printf("%I64d\n",calc(R)-calc(L-));
}
return ;
}