二进制翻转（rev）3

给定 $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}$ 表示：

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

写成代码长这样：

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

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

观察所有的状态，容易发现这样一件事情：$i,j,k,p$ 都难以优化，只有这个 $v$ 搞特殊，作用仅限于统计答案。

我们当然希望我们的 DP 和谐统一，于是我们要消除 $v$ 的影响。

首先看有关 $v$ 的位置：

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;
}

这里 $v$ 的作用是处理低位对高位的进位。

然而 $v$ 真的有用吗？

观察我们的转移，可以发现：当 $i_0=i_1$，即 $len$ 为奇数时，所有的状态必定满足 $k=i=step$。那么此时无论如何，下面有关 $v$ 的判断将会毫无用处，所以可以省略。

那么中点就在偶数的时候了：这个 $v$ 到底补充了哪一部分的答案？

类似的，由上上篇题解可知，这个 $v$ 是用来处理低位对高位的进位的，那么什么时候在长度为偶数的时候会有低位对高位的进位且没有被处理？

经过仔细观察，我们得出结论：没有被处理的进位是，当 $i_0=i_1+1$（即最内层的状态）时，$i_1$ 向 $i_0$ 进位且 $i_0$ 在没有接受 $i_1$ 的进位的前提下，这一位的和为 $1$（即代码中的 $t=1$），那么此时就会产生 $i-nk$ 的贡献。

那么我们就解决了这个问题，只需要在 $i_0=i_1+1$ 时加入特判，就能解决这个问题。

具体的，当 $nj=1\land t=1\land i_0=i_1+1$ 时，有 $tmp\leftarrow tmp-(i-nk)$。

然后你就成功的省去了第 $4$ 维度。

代码非常快，所有点都是 $2ms$ 过。

#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][3];
ll g[N][2][N][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][1]=1;
    rep(i,1,len2){
        int i0=len-i+1,i1=i;
        rep(j,0,1)rep(k,0,len2)rep(p,0,2){
            ll cnt=f[i-1][j][k][p];
            ll sum=g[i-1][j][k][p];
            if(!cnt)continue;
            for(int h=0;h<2;h++){
                int 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;
                    nk=i;
                    f[i][nj][nk][np]+=cnt;
                    g[i][nj][nk][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;
                        if(t!=1){
                            if(t==2)tmp-=i-k;
                            nk=i;
                        }
                        if(i0==i1+1){
                            if(nj==1){
                                if(t==1){
                                    tmp-=i-nk;
                                }
                            }
                        }
                        f[i][nj][nk][np]+=cnt;
                        g[i][nj][nk][np]+=sum+cnt*tmp;
                    }
                }
            }
        }
    }
    ll ans=0;
    rep(j,0,1)rep(k,0,len2)rep(p,0,2){
        if(p==2)continue;
        ll cnt=f[len2][j][k][p];
        ll sum=g[len2][j][k][p];
        if(!cnt)continue;
        ans+=sum;
    }
    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;
}

应该是信息极限了，估计不能继续优化了。