题目2 : 二进制翻转
时间限制:20000ms
单点时限:1000ms
内存限制:256MB
描述
定义函数 Rev(x) 表示把 x 在二进制表示下翻转后的值
例如：
Rev(4)=1，因为 4 等于(100)B，翻转后是 (001)B，也就是 1
Rev(6)=3，因为 6 等于(110)B，翻转后是 (011)B，也就是 3
定义 Cnt(x) 表示 x 在二进制表示下 1 的个数，求：
输入
仅一行，一个非负整数 n
0 ≤ n ≤ 1015
输出
仅一行：一个非负整数表示答案
- 样例输入
-
2
- 样例输出
-
3
/* 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; }