1 /* 2 * algorithm : math 3 * 4 * Memory 392K Time 0MS Language G++ 5 * 6 * code by : zhyu 7 */ 8 #include <cstdio> 9 10 const int N = 31; 11 12 int c[N][N],pow2[N]; 13 bool bin[N]; 14 15 inline void init(void) 16 { 17 for(int i=0;i<N;i++) c[i][0]=c[i][i]=1,pow2[i]=(1<<i); 18 for(int i=2;i<N;i++) 19 for(int j=1;j<i;j++) 20 c[i][j]=c[i-1][j-1]+c[i-1][j]; 21 } 22 int gao(int x) 23 { 24 if(x<=1) return 0; 25 int i,j,k,n1,n0,len,res=0; 26 for(i=0;i<N;i++) bin[i]=((pow2[i]&x)!=0); 27 for(i=N-1;i>=0 && bin[i]==0;i--); 28 for(len=i;len>=1;len--) 29 if(len&1) res+=((pow2[len-1]-c[len-1][(len-1)/2])>>1); 30 else res+=(pow2[len-1]>>1); 31 for(j=i,n0=n1=0;j>=0;j--) 32 if(bin[j]) n1++; 33 else n0++; 34 if(n1<=n0) res++; 35 for(j=i-1,n0=0,n1=1;j>=0;j--) 36 if(bin[j]) 37 { 38 for(k=j;k>=0 && k+n0+1>=j-k+n1;k--) res+=c[j][k]; 39 n1++; 40 } 41 else n0++; 42 return res; 43 } 44 int main(void) 45 { 46 init(); 47 int st,ed; 48 scanf("%d%d",&st,&ed); 49 printf("%d\n",gao(ed)-gao(st-1)); 50 return 0; 51 }
有很多值得学习的地方