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

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