题目2 : 二进制翻转

/*    Name: rev x& count num 1 of x in binary    Copyright: @2017 shenben    Author: shenben    Date: 25/04/17 16:47    Description://枚举当前要计算的数的位数，考虑从左右往中间dp//f[i][j][k][cmp1][cmp2]表示考虑了前 i 位和后 i 位，前 i 位需要 j 个进位，后 i 位的进位为 k，前 i 位和后 i 位和上限的大小情况分别是 cmp1，cmp2//转移时，同时枚举第 i+1 位和倒数第 i+1 位的值，枚举该位最后是否是 1 ，根据这个判断是否需要进位即可//时间复杂度 O((logn)^2)//(来自官方题解)     */#include<cstdio>#include<cstring>#include<cstdlib>#include<iostream>#include<algorithm>using namespace std;typedef long long ll;const int N=55;ll n,ans;int m,dig[N];ll f[N][N][2][3][2];ll s[N][N][2][3][2];inline int fun(int b,int x,int y){    if(x==y) return b;    if(x<y) return 2;    return 0;}void solve(){    memset(f,0,sizeof f);    memset(s,0,sizeof s);    if(m==1){ans++;return ;}    f[1][1][0][fun(1,0,dig[1])][0]=1;    f[1][0][0][fun(1,1,dig[1])][1]=1;    s[1][1][0][fun(1,0,dig[1])][0]=2;    s[1][0][0][fun(1,1,dig[1])][1]=2;    for(int i=2;i<=m/2;i++){        for(int j=0;j<=m;j++){            for(int a=0;a<2;a++){                for(int b=0;b<3;b++){                    for(int c=0;c<2;c++){                        ll k=f[i-1][j][a][b][c];                        ll l=s[i-1][j][a][b][c];                        if(!k) continue;                        //0,0                        f[i][0][a|(dig[m-i+1]==1)][fun(b,0,dig[i])][0]+=k;                        s[i][0][a|(dig[m-i+1]==1)][fun(b,0,dig[i])][0]+=l;                        //0,1                        f[i][j+1][a|(dig[m-i+1]==1)][fun(b,1,dig[i])][c]+=k;                        s[i][j+1][a|(dig[m-i+1]==1)][fun(b,1,dig[i])][c]+=l+k*(2-c);                        if(a|(dig[m-i+1]==1)){                            //1,0                            f[i][j+1][a][fun(b,0,dig[i])][c]+=k;                            s[i][j+1][a][fun(b,0,dig[i])][c]+=l+k*(2-c);                            //1,1                            f[i][0][a][fun(b,1,dig[i])][1]+=k;                            s[i][0][a][fun(b,1,dig[i])][1]+=l+k*(2-j);                        }                    }                }            }        }    }    if(m&1){        int i=m+1>>1;        for(int j=0;j<=m;j++){            for(int a=0;a<2;a++){                for(int b=0;b<3;b++){                    for(int c=0;c<2;c++){                        ll k=f[i-1][j][a][b][c];                        ll l=s[i-1][j][a][b][c];                        if(!k) continue;                        //0                        f[i][0][a|(dig[m-i+1]==1)][b][0]+=k;                        s[i][0][a|(dig[m-i+1]==1)][b][0]+=l;                        //1                        if(a|(dig[m-i+1]==1)){                            f[i][0][a][b][0]+=k;                            s[i][0][a][b][0]+=l+k*(1-j);                        }                    }                }            }        }    }    int i=m+1>>1;    for(int j=0;j<=m;j++){        for(int a=0;a<2;a++){            for(int b=0;b<3;b++){                for(int c=0;c<2;c++){                    if(!a&&!b) continue;                    ll k=f[i][j][a][b][c];                    ll l=s[i][j][a][b][c];                    if(!k) continue;                    ans+=l;                    if(c) ans-=k*j;                }            }        }    }    }int main(){    cin>>n;    for(ll t=n;t;t>>=1) dig[++m]=t&1;    for(solve();--m;){        for(int i=1;i<=m;i++) dig[i]=1;        solve();    }    cout<<ans;    return 0;}