二进制翻转（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;
}

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

二进制翻转（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;
}

二进制翻转（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;
}

二进制翻转（rev）4

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

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

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

首先先写出我们的状态定义：

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

• 考虑了高位 $i$ 和低位 $i$ 及以前的数位；
• 低位 $i$ 受到的进位 $j=0/1$；
• 高位 $i$ 以前最后一个 $0$ 的位置 $k$；
• 高低位与限制的关系 $p=0/1/2$。

写成代码长这样：

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

看起来维度很高，但是实际上这里面很多都可以优化掉（目前我优化掉了一个 $\log n$ 的空间）。

观察所有的状态，容易发现这样一件事情：$i,j,p$ 都难以优化，只有这个 $k$ 搞特殊，作用仅限于进位，但是却非要占领 $\log n$ 的时间空间。

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

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

if(t==2)tmp-=len2-1-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;
    }
  }
}

总结 $k$ 的作用：当高位出现进位的时候，需要将中间的一段全部进位。

那么为什么我不能在处理那一位的时候就提前钦定是否出现进位呢？

具体的，定义一个状态 $i$ 会被“清算”当且仅当后面的第一个 $0$ 会触发进位。状态 $i$ 发动“大清洗”当且仅当其高位 $i$ 会进位使得前面的数被“清算”。

那么我们不妨改变状态 $k$ 的定义：$k=0$ 表示该点日后不会被“清算”，$k=1$ 表示该点日后会被“清算”；特别的，当状态 $i$ 的高位 $i$ 为 $0$ 或者当前为最后一位时强制令 $k=0$。

同时我们为了好处理，额外加一维度（后面会优化掉）$v=0/1$ 表示高位 $i$ 的值（真的是值）。

那么统计答案当然没有区别，重点是如何转移。

Case #1

我们先看 $i_0=i_1$ 时的情况：

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

首先我们看一下“大清洗”的位置：if(t==2)。

这里我们发现会清算所有在我之前（不含我）且在上一个 $0$ 之后的位置进行清算。

然而我们注意到：状态里 $k$ 的定义是提前钦定是否出现进位，且在当前的 $f/g$ 中已经处理了“清算”带来的影响。

由于状态 $i$ 本身不受影响，于是这一行可以直接删除。

然后看需要特殊处理的部分：因为当 $t=0$ 是不会发动“大清洗”，其以前的所有数不会被清算；$t=1$ 则会发动，清算其以前的所有数。

于是我们就会发现：

• 当 $k=1$，即前一位被清算时，如果这一位 $t=0$，那么此时状态不合法，因为前一位实际上不会被清算。
• 当 $k=0$ 且 $v=1$，即前一位有值且会被清算（因为如果前一位是 $0$ 的话不会有任何限制，作用相当于滚木）时，若 $t=2$，则此时状态不合法，因为这一位会发动“大清洗”。

因此需要特判这两种情况：

                    if(k&&t!=2)continue;
                    if(!k&&v&&t==2)continue;

最后由于这是最后一位，因此强制钦定转移到 $k=0$ 即可。

                    nk=0;
                    f[i][nj][nk][t+j&1][np]+=cnt;
                    g[i][nj][nk][t+j&1][np]+=sum+cnt*tmp;

Case #2

接着看其余普通情况：

                        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;

首先我们先特判不合法状态：

• 当 $k=0 \land v=1$ 时，若 $t=2$ 或者 $i_0=i_1+1$ 且 $t=1\land nj=1$，那么这种情况不合法。
• 当 $k=1$ 时，若此时会结算前面的清算（$t=0\lor t=2$）或者为最后一位，但是并不满足“大清洗”条件（$t=2$ 或者 $i_0=i_1+1$ 且 $t=1\land nj=1$），那么也不合法。

                        if(!k&&v&&(t==2||i0==i1+1&&nj==1&&t==1))continue;
                        if(k&&(t==0||t==2||i0==i1+1)&&!(t==2||i0==i1+1&&nj==1&&t==1))continue;

接着看转移的 tmp：初始时肯定跟原来的 2*t-nj 一样，然后我们需要考虑清算的影响。

考虑什么时候会触发清算：这个前面已经提到，当 $t=1\lor i_0=i_1+1\land nj=1\land t=1$ 时。那么由于这里触发的进位，所以这种时候需要 tmp--。

最后看转移对象：$i,j,v,p$ 肯定可以轻松确定，主要问题在于 $k$ 怎么转移。

Case #2.1

若转移目标 $nextk=0$，即 $f_{i,nj,0,nv,np}\leftarrow f_{i,j,k,v,p}$，那么要满足下列条件中的一个：

• 上一个位置没有被清算，即 $k=0$；
• 这个位置的 $k$ 必须为 $0$（$t=0\lor t=2\lor i_0=i_1+1$）。

那么只要满足这两个条件之一，就可以进行转移：

                        if(!(nk==1&&k==1)){
                            f[i][nj][0][t&1][np]+=cnt;
                            g[i][nj][0][t&1][np]+=sum+cnt*tmp;
                        }

Case #2.2

若转移目标 $nextk=1$，那么转移必须满足：

• 这个状态不是必须为 $0$；
• 上一个状态不满足 $k=0\land v=1$。

那么可以这样写：

                        if(nk&&!(!k&&v)){
                            --tmp;
                            f[i][nj][1][t&1][np]+=cnt;
                            g[i][nj][1][t&1][np]+=sum+cnt*tmp;
                        }

总结

这样我们就完成了 $\mathcal{O}(\log^3n)$ 到 $\mathcal{O}(\log^2n)$ 的优化。

代码：

#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][2][2][3];
ll g[N][2][2][2][3];
//0: high-not-close
//1: high-close and low <=
//2: high-close and low >
#define cmp(I,J,K,V,P) if(i==I&&j==J&&k==K&&v==V&&p==P)
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,1)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 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(k&&t!=2)continue;
                    if(!k&&v&&t==2)continue;
                    nk=0;
                    f[i][nj][nk][t+j&1][np]+=cnt;
                    g[i][nj][nk][t+j&1][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=1;
                        if(!k&&v&&(t==2||i0==i1+1&&nj==1&&t==1))continue;
                        if(k&&(t==0||t==2||i0==i1+1)&&!(t==2||i0==i1+1&&nj==1&&t==1))continue;
                        if(t==2||t==0||i0==i1+1){
                            nk=0;
                            tmp-=(t==2||i0==i1+1&&nj==1&&t==1);
                        }
                        if(!(nk==1&&k==1)){
                            f[i][nj][0][t&1][np]+=cnt;
                            g[i][nj][0][t&1][np]+=sum+cnt*tmp;
                        }
                        if(nk&&!(!k&&v)){
                            --tmp;
                            f[i][nj][1][t&1][np]+=cnt;
                            g[i][nj][1][t&1][np]+=sum+cnt*tmp;
                        }
                    }
                }
            }
        }
    }
    ll ans=0;
    rep(j,0,1)rep(k,0,0)rep(v,0,1)rep(p,0,1){
        ll cnt=f[len2][j][k][v][p];
        ll sum=g[len2][j][k][v][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;
}

后记

很显然 $k,v$ 可以向之前的 $p,q$ 一样压在一起，因为 $k=1$ 时 $v$ 没有用处。

#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][3][3];
ll g[N][2][3][3];
//k0: K=0 & V=0
//k1: K=0 & V=1
//k2: K=1
//0: high-not-close
//1: high-close and low <=
//2: high-close and low >
#define cmp(I,J,K,V,P) if(i==I&&j==J&&k==K&&v==V&&p==P)
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,2)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(k==2&&t!=2)continue;
                    if(k==1&&t==2)continue;
                    nk=0;
                    f[i][nj][t+j&1][np]+=cnt;
                    g[i][nj][t+j&1][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=1;
                        if(k==1&&(t==2||i0==i1+1&&nj==1&&t==1))continue;
                        if(k==2&&(t==0||t==2||i0==i1+1)&&!(t==2||i0==i1+1&&nj==1&&t==1))continue;
                        if(t==2||t==0||i0==i1+1){
                            nk=0;
                            tmp-=(t==2||i0==i1+1&&nj==1&&t==1);
                        }
                        if(!(nk==1&&k==2)){
                            f[i][nj][t&1][np]+=cnt;
                            g[i][nj][t&1][np]+=sum+cnt*tmp;
                        }
                        if(nk&&!(k==1)){
                            --tmp;
                            f[i][nj][2][np]+=cnt;
                            g[i][nj][2][np]+=sum+cnt*tmp;
                        }
                    }
                }
            }
        }
    }
    ll ans=0;
    rep(j,0,1)rep(k,0,1)rep(p,0,1){
        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;
}

最终的状态：

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

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

要算 $\sum_{i=0}^{n}\mathrm{Cnt}(\mathrm{Rev}(i)+i)$，反过来按位统计：对每一位 $b$，数一数有多少个 $i\le n$ 使得 $\mathrm{Rev}(i)+i$ 的第 $b$ 位是 $1$，加起来就是答案。

关键在于 $i+\mathrm{Rev}(i)$ 的进位结构。设 $i$ 的二进制长度为 $m$，$\mathrm{Rev}$ 把第 $j$ 位搬到第 $m-j+1$ 位，所以

$(i+\mathrm{Rev}(i))$ 的第 $j$ 位，只由「第 $j$ 位与第 $m-j+1$ 位」这一对、以及从更低位的进位决定。

于是把 $i$ 的位从两端配对，从最低位那一对开始逐对做数位 DP。处理到第 $i$ 对（第 $i$ 位配第 $m-i+1$ 位）时，状态里要记：

• 进位：这一对相加后往下一对传的进位，以及这一对自身产生的 $1$ 的个数；
• 比较关系：已经把两端的位定下来之后，$i$ 与 $\mathrm{Rev}(i)$ 谁更大（三种：小于/等于/大于），后面确定「还贴着 $n$ 的上界」的那部分时要用；
• 上界：高半部分是否还顶在 $n$ 的对应位上（顶住了就不能随便填 $1$）。

DP 里同时维护两个量：方案数和已经统计到的 $1$ 的个数之和。转移时新增的 $1$ 的个数乘上方案数累加进去，这样最后得到的就是「所有合法 $i$ 的位数之和」。逐位统计与整体统计是一回事，因为每一位的贡献都能在配对到它时结算。

$n$ 的位数是 $m$，还要把长度 $1,2,\dots,m-1$ 的 $i$（即二进制全是 $1$、且长度不足 $m$）单独用同样的 DP 累加一遍。

复杂度 $O(m^2)$ 级别（状态里那个「$1$ 的个数」一维只到 $m$）。

#include <cstdio>
#include <cstring>
#define N 55
#define LL long long

int m;          // n 的二进制位数
int dgt[N + 1]; // n 的二进制位，dgt[1] 是最低位
int lmt[N + 1]; // 这一轮用的上界，lmt[1] 是最低位
LL ans;

// f[第几步][进位][上一个「对位和不为 1」的位置][它的值][是否已经小于上界][低位与上界的比较]
LL f[N][2][N][3][2][3];
LL sum[N][2][N][3][2][3]; // 同一状态里「已经算出的那部分答案」之和

// 把所有「二进制长度恰为 len、且不超过 lmt[1..len]」的 v 的
//   Σ popcount(v + Rev(v)) = Σ ( 2 * popcount(v) - 做加法产生的进位个数 )
// 一次算出来。做法是把 v 的位从两端配对，从最低的一对开始逐对确定。
LL calc(int len) {
    int step = (len + 1) / 2;             // 配对的步数
    int tp = (len & 1) ? step - 1 : step; // 反向清点进位时要看到的最大下标
    memset(f, 0, sizeof f);
    memset(sum, 0, sizeof sum);
    f[0][0][0][0][0][1] = 1; // 进位 0；还没碰到对位和不为 1 的位；贴着上界；低位相等
    for (int j = 1; j <= step; j++) {
        int hi = len - j + 1, lo = j; // 这一步要确定的两条位
        for (int c = 0; c < 2; c++) {
            for (int p = 0; p <= step; p++) {
                for (int v = 0; v < 3; v++) {
                    for (int a = 0; a < 2; a++) {
                        for (int b = 0; b < 3; b++) {
                            LL k = f[j - 1][c][p][v][a][b];
                            LL acc = sum[j - 1][c][p][v][a][b];
                            if (!k) continue;
                            for (int h = 0; h < 2; h++) {
                                if (j == 1 && h == 0) continue; // 最高位必须是 1
                                int na;
                                if (a || h < lmt[hi]) {
                                    na = 1; // 已经松了，或这一位比上界小 ⇒ 低位随便填
                                } else if (h == lmt[hi]) {
                                    na = 0; // 还贴着上界
                                } else {
                                    continue; // 贴着还填大了 ⇒ v > n，整条砍掉
                                }
                                if (hi == lo) {
                                    // 正中间那一位，自己和自己配对
                                    int ps = h + h, nc = (ps + c) >> 1;
                                    LL add = ps - nc;
                                    if (ps == 2) add -= (step - 1) - p; // 反向那半里的进位个数
                                    int nv = ps ? 2 : 1;
                                    f[j][nc][j][nv][na][b] += k;
                                    sum[j][nc][j][nv][na][b] += acc + k * add;
                                } else {
                                    for (int l = 0; l < 2; l++) {
                                        int ps = h + l, nb;
                                        if (l < lmt[lo]) {
                                            nb = 2;
                                        } else if (l > lmt[lo]) {
                                            nb = 0;
                                        } else {
                                            nb = b;
                                        }
                                        int nc = (ps + c) >> 1;
                                        LL add = 2 * ps - nc;
                                        int np = p, nv = v;
                                        if (ps != 1) {
                                            if (ps == 2) add -= j - p;
                                            np = j;
                                            nv = ps ? 2 : 1;
                                        }
                                        f[j][nc][np][nv][na][nb] += k;
                                        sum[j][nc][np][nv][na][nb] += acc + k * add;
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    LL res = 0;
    for (int c = 0; c < 2; c++) {
        for (int p = 0; p <= step; p++) {
            for (int v = 0; v < 3; v++) {
                for (int a = 0; a < 2; a++) {
                    for (int b = 0; b < 3; b++) {
                        if (!a && !b) continue; // 贴着上界、低位又更大 ⇒ v 超过上界
                        LL k = f[step][c][p][v][a][b];
                        LL acc = sum[step][c][p][v][a][b];
                        if (!k) continue;
                        LL cut = 0;
                        if (v == 2 && tp > p) cut = tp - p;
                        res += acc - k * cut;
                    }
                }
            }
        }
    }
    return res;
}

int main() {
    // freopen("rev.in", "r", stdin);
    // freopen("rev.out", "w", stdout);
    LL n;
    scanf("%lld", &n);
    LL t = n;
    while (t) {
        dgt[++m] = (int)(t & 1);
        t >>= 1;
    }
    for (int len = 1; len < m; len++) {
        for (int i = 1; i <= len; i++) lmt[i] = 1; // 长度不足 m 的 v 必定不超过 n，上界按全 1 算
        ans += calc(len);
    }
    for (int i = 1; i <= m; i++) lmt[i] = dgt[i]; // 长度恰为 m 的 v 要不超过 n
    ans += calc(m);
    printf("%lld\n", ans);
    return 0;
}