二进制翻转（rev）

给定 $n\le 10^{15}$，定义 $r(i)$ 表示 $i$ 二进制翻转后的结果，$c(i)$ 表示 $i$ 二进制下 $1$ 的个数，求：

$$\sum_{i=0}^n c(i+r(i))$$

显然的数位 DP。

由于有翻转的存在，我们的数位 DP 的阶段 $i$ 应该表示同时包含低位 $i$ 和高位 $i$ 的状态。

并且，由于 $+$ 的存在，数位 DP 同时应该包含低位 $i$ 的受到进位状态 $j=0/1$。

然后，考虑到高位 $i$ 也有进位。但是由于我们的数位 DP 在高位来看是倒着的，于是我们应该模仿传统加法模拟进位：记录 $k$ 表示高位 $i$ 之前最后一个进位的位置。那么转移的时候只需要将中间的所有 $1$ 变为 $0$ 并计算代价即可。

接着，由于低位也可以向高位进位；同时这个 DP 具有对称性，所以我们可以一眼看出如下结论：如果状态 $k$（注意这个 $k$ 是上面的那个 $k$）对应的低位有进位，那么一定会导致状态 $k$ 的低位高位之间的所有 $1$ 变为 $0$。因此，我还有记录 $v=0/1/2$ 表示没有为 $0$ 的位，有但是没有进位，以及有且有进位。

最后由于有一个数位限制，且我们的 DP 只能限制高位，所以我们要记录状态：$p=0/1,q=0/1/2$，分别表示高位是否贴着数位限制，以及低位与数位限制的关系（$>,=,<$）。

因此，我们得出结论：

定义 $f_{i,j,k,v,p,q}$ 表示：

• 考虑了高位 $i$ 和低位 $i$ 及以前的数位；
• 低位 $i$ 受到的进位 $j=0/1$；
• 高位 $i$ 以前最后一个 $0$ 的位置 $k$；
• 状态 $k$ 不存在，存在但没有进位，以及存在有进位，$v=0/1/2$；
• 高位有没有数位限制 $p=0/1$；
• 低位和数位限制的关系 $q=0/1/2$；

$f$ 就是满足这些的数的数量。

$g$ 是满足这些限制的数的 $c$ 的和。

转移需要枚举所有状态，然后枚举高位值 $h$ 并分类讨论。

如果高低位不重合，那么枚举低位值 $l$。

记 $nj,nk,nv,np,nq$ 分别表示从 $(i-1,j,k,v,p,q)$ 转移到的下一个状态。

首先 $np,nq$ 是十分简单的，模拟即可。

然后就是 $nj$：记 $t=h+l$，那么显然 $nj=\lfloor\frac{t+j}{2}\rfloor$。

接着是 $nk,nv$：当 $t\ne 1$ 时，$nk$ 要更新，连带着 $nv$ 也要更新。

具体怎么更新呢？我们分类讨论：

• $t=2$：此时高位 $i$ 有进位，我们需要去掉上一个 $0$ 的位置到这里所有的数的贡献，即 $k-i$。然后令 $nk=i,nv=2$ 即可。
• $t=0$：此时没有，那么直接 $nk=i,nv=1$ 就行。

这些讨论完直接转移就行了。

如果重合，和上面是类似的。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,s,t) for(int i=s;i<=t;i++)
const int N=55;
int n,lim[N],dig[N],m;
//f[step][to][last_0][last_0_type][limit][low cmp limit]
int f[N][2][N][3][2][3];
int g[N][2][N][3][2][3];
int calc(int len){
    int len2=len+1>>1;
    int tlen=(len&1)?len2-1:len2;
    memset(f,0,sizeof(f));
    memset(g,0,sizeof(g));
    f[0][0][0][0][0][1]=1;
    rep(i,1,len2){
        int i0=len-i+1,i1=i;
        rep(j,0,1)rep(k,0,len2)rep(v,0,2)rep(p,0,1)rep(q,0,2){
            int cnt=f[i-1][j][k][v][p][q];
            int sum=g[i-1][j][k][v][p][q];
            if(!cnt)continue;
            for(int h=0;h<2;h++){
                int nv,np,nq,nk,nj;
                if(i==1&&h==0)continue;
                if(p||h<lim[i0])np=1;
                else if(h==lim[i0])np=0;
                else continue;
                if(i0==i1){
                    int t=h+h;
                    nj=t+j>>1;
                    int tmp=t-nj;
                    if(t==2)tmp-=len2-1-k;
                    nv=t?2:1;
                    nk=i;
                    f[i][nj][nk][nv][np][q]+=cnt;
                    g[i][nj][nk][nv][np][q]+=sum+cnt*tmp;
                }
                else{
                    for(int l=0;l<2;l++){
                        if(l<lim[i1])nq=2;
                        else if(l>lim[i1])nq=0;
                        else nq=q;
                        int t=h+l;
                        nj=t+j>>1;
                        int tmp=2*t-nj;
                        nk=k,nv=v;
                        if(t!=1){
                            if(t==2)tmp-=i-k;
                            nk=i;
                            nv=t?2:1;
                        }
                        f[i][nj][nk][nv][np][nq]+=cnt;
                        g[i][nj][nk][nv][np][nq]+=sum+cnt*tmp;
                    }
                }
            }
        }
    }
    int ans=0;
    rep(j,0,1)rep(k,0,len2)rep(v,0,2)rep(p,0,1)rep(q,0,2){
        if(!p&&!q)continue;
        int cnt=f[len2][j][k][v][p][q];
        int sum=g[len2][j][k][v][p][q];
        if(!cnt)continue;
        int tmp=0;
        if(v==2&&tlen>k)tmp+=tlen-k;
        ans+=sum-tmp*cnt;
    }
    return ans;
}
signed main(){
    scanf("%lld",&n);
    int ans=0,t=n;
    while(t)dig[++m]=t&1,t>>=1;
    rep(i,1,m-1){
        rep(j,1,m)lim[j]=1;
        ans+=calc(i);
    }
    rep(j,1,m)lim[j]=dig[j];
    ans+=calc(m);
    printf("%lld",ans);
    return 0;
}