【题解】1的个数

题意

给你 $01$ 字符串的生成规则，问你 $S_n$ 第 $[L,R]$ 位上 $1$ 的个数。生成规则如下：

$S_1=1$
$S_2=010$
$S_3=1011101$
$S_n=\overline{S_{n-1}+0+S_{n-1}},n\geq 2$
这里 $\overline{x}$ 表示将 $x$ 的值取反，即 $x$ 中的 $1$ 变为 $0$ ， $0$ 变为 $1$ 。

题解

首先我们可以得到 $S_n$ 的长度为 $2^n-1$ ，因为长度是 $2*|S_{n-1}|+1$ 递推下去就可以得到了。然后因为取反的性质两次取反等于没取反，稍微打一下表会会发现 $S_i$ 和 $S_{i+1}$ ( $i$ 为奇数)中 $1$ 的个数是一样多的。我们只把奇数部分打印出来可以得到

1:  1
5:  1011101
21: 1011101010111011101110101011101
85: 1011101010111011101110101011101010111010101110111011101010111011101110101011101110111010101110101011101010111011101110101011101
...

会发现若 $S_{i-1}$ 中 $1$ 个数为 $a$ 的话，那么 $S_i$ 中 $1$ 的个数就为 $a*4+1$ 。
那么我们可以先打一个关于 $S_i$ 中 $1$ 的个数的表打到超过 $10^{18}$ 为止。
由于 $S_n$ 的长度是以指数的形式增长的，所以题目中的 $n\leq 10^{18}$ 其实没什么关系，由于是递推生成的，对于 $S_i$ 的 $[1,m]$ 的部分也是可以递推回去的，这个时候就可以用递归来做了，为 $[1,m]$ 的含有为某个 $S_i$ 作为前缀。
要求求解 $S_n$ 中的 $[L,R]$ 的部分有多少个 $1$ ，即让求 $S_n$ 中的 $[1,R]$ 中有多少个 $1$ 减去 $[1,L-1]$ 有多少个 $1$ 。
以求 $[1,R]$ 为例，我们先找到中心记为 $x$ ，那么可以分为两部分 $[1,x-1]$ 和 $[x+1,R]$ ，第一部分可以用查表来获取 $1$ 的个数，第二部分我们就递归下去，但是需要注意的是，你找前缀的时候，这个前缀的奇偶性可能和你给你 $n$ 是不同的，这个时候就要考虑查表的值了，若是相同的我们就直接用查表的值，否则我们就得用前缀的长度减去查表的值，即取反操作。

复杂度

时间复杂度 $O(logn)$

代码

#include<bits/stdc++.h>
using namespace std;
const long long MAX=1e18;
long long f[]={0,1,1,5,5,21,21,85,85,341,341,1365,1365,5461,5461,21845,21845,87381,87381,349525,349525,1398101,1398101,5592405,5592405,22369621,22369621,89478485,89478485,357913941,357913941,1431655765,1431655765,5726623061,5726623061,22906492245,22906492245,91625968981,91625968981,366503875925,366503875925,1466015503701,1466015503701,5864062014805,5864062014805,23456248059221,23456248059221,93824992236885,93824992236885,375299968947541,375299968947541,1501199875790165,1501199875790165,6004799503160661,6004799503160661,24019198012642645,24019198012642645,96076792050570581,96076792050570581,384307168202282325,384307168202282325,1537228672809129301};
string s[20];
long long dfs(long long n,int flag)
{
    if(n==0)
        return 0;
    if(n==1&&flag)
        return 1;
    else if(n==1)
        return 0;
    long long m=0,ans,cnt=0;
    while(m<n)
        m=m*2+1,cnt++;
    if(cnt%2==flag)
    {
        ans=(f[cnt]-1)/2;
    }
    else
    {
        ans=(f[cnt]-1)/2;
        ans=(m-1)/2-ans;
    }
    m=(m-1)/2;
    long long res=n-m-1;
    if(cnt%2==flag)
        return ans+1+dfs(res,flag);
    else
        return ans+dfs(res,flag);
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        long long n,l,r;
        scanf("%lld%lld%lld",&n,&l,&r);
        printf("%lld\n",dfs(r,n%2)-dfs(l-1,n%2));
    }
    return 0;
}