二进制翻转（rev）2

二进制翻转（rev）2

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

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

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

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

定义 fi,j,k,v,p,qf_{i,j,k,v,p,q} 表示：

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

写成代码长这样：

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

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

Part I.

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

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

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

代码片段：

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

1
2
3
4
5
6
7
8
9
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.

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

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

代码片段：

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

1
2
3
4
5
6
7
8
9
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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=1p=1，那么对于第 66 维 qq 的值完全不重要！

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

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

这样就可以完成优化！

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

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#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;
}