HDU5694-BD String-数学归纳找规律

题目：

众所周知，度度熊喜欢的字符只有两个：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 的个数是多少？

L，R<10^18

思路

可以通过观察前面一个字符串是后一个字符串的前缀，也就是s(n)中包含前面所有的字符串。所以其实可以只考虑一个字符串，s（2^1000）字符串早就超出10^18所以根本不用考虑，只要考虑10^18以内就OK了。

继续推导，L到R的B的数量，可以表示成，sumb（R）-sumb（L-1）;

接下来就是如何求sumb（x）

如果x=2^p 则sumb（x）=2^(p-1)+1;否则sumb（x）=2^(p-1)+1-sumd（2^p-x-1）-1;

(这里说明一下x到2^p的那段距离就是这个字符串的前缀只不过前后反转，bd互调，所以这里减去了sumd)

同样sumd的求发

如果x=2^p 则sumd（x）=2^(p-1)-1;否则sumd（x）=2^(p-1)-1-sumb（2^p-x-1）;

#include<bits/stdc++.h>
using namespace std;
long long b[100];
long long sumb(long long x);
long long sumd(long long x);
long long sumb(long long x) {
    if(x==0) return 0;
    if(x==1) return 1;
    long long tt=1;
    int i=0;
    while(tt<x) {
        tt*=2;
        i++;
    }
    if(tt==x) {
        return b[i-1]+1;
    }
    else {
        return b[i-1]+1-sumd(tt-x-1)-1;
    }
}
long long sumd(long long x) {
    if(x==0) return 0;
    if(x==1||x==2) return 0;
    long long tt=1;
    int i=0;
    while(tt<x) {
        tt*=2;
        i++;
    }
    if(tt==x) {
        return b[i-1]-1;
    }
    else {
        return b[i-1]-1-sumb(tt-x-1);
    }

}
int main()
{
    int t;
    b[0]=1;
    for(int i=1;i<=62;i++) b[i]=b[i-1]*2;
    long long l,r;
    scanf("%d",&t);
    while(t--) {
        scanf("%lld%lld",&l,&r);
        printf("%lld\n",sumb(r)-sumb(l-1));
    }
    return 0;
}