二进制翻转（rev）2

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

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

本题解建立在上一篇题解的基础上进行了一些优化。

首先写出上一篇题解的状态设计：

定义 $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$；

写成代码长这样：

int f[N][2][N][3][2][3];

看起来维度很高，但是实际上这里面很多都可以优化掉（目前我优化掉了 $\frac{2}{3}$ 的空间）。

Part I.

我们观察状态和转移，可以发现如下事实：对于第 $4$ 维状态 $v$，它的影响仅限于统计答案时做的修正，而这种修正的发生当且仅当 $v=2$！也就是说，$v=0/1$ 在整个 DP 过程中，尽管表示的意思不同，但是作用一样！

所以我们就可以改变状态设计：$v=0/1$ 表示状态 $k$ 不存在或存在但没有进位，以及存在有进位。

这样就可以成功使得空间 $\times\frac{2}{3}$。

代码片段：

ll f[N][2][N][2][2][3];

    rep(j,0,1)rep(k,0,len2)rep(v,0,1)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==1&&tlen>k)tmp+=tlen-k;
        ans+=sum-tmp*cnt;
    }

Part II.

沿用上面的思路，我们又可以发现这样一件事：第 $6$ 维 $q$ 的作用也仅限于统计答案时排除不合法状态，而这种情况发生当且仅当 $q=0$！因此我们可以合并 $q=1/2$：当 $q=0$ 时表示低位 $>$ 限制，$q=1$ 时表示低位 $\le$ 限制。

这样我们有成功优化 $\times\frac{2}{3}$！

代码片段：

int f[N][2][N][2][2][2];

    rep(j,0,1)rep(k,0,len2)rep(v,0,1)rep(p,0,1)rep(q,0,1){
        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==1&&tlen>k)tmp+=tlen-k;
        ans+=sum-tmp*cnt;
    }

                    for(int l=0;l<2;l++){
                        if(l<lim[i1])nq=1;
                        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?1:0;
                        }
                        f[i][nj][nk][nv][np][nq]+=cnt;
                        g[i][nj][nk][nv][np][nq]+=sum+cnt*tmp;
                    }

Part III.

似乎到极限了吗？并不是，我们继续观察，又可以发现这样一件事情：如果说 $p=1$，那么对于第 $6$ 维 $q$ 的值完全不重要！

因此我们可以把这两维合并为 $1$ 维：

• 当高位没有贴紧限制时 $p=0$；
• 当高位贴近限制且低位 $\le$ 限制时 $p=1$；
• 当高位贴近限制且低位 $>$ 限制时 $p=2$。

这样就可以完成优化！

到这里我们的空间就变为了原来不优化的代码的 $\frac{1}{3}$ 了！而且状态还少一维！

代码：

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