poj 3252

设x化为二进制长度为len.例如x=1100b
1、先求长度小于len的和
2、求长度为len且小于x的个数和。此时可以枚举二进制x中1的位置，将其变为0后满足的数的个数和。
View Code
  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #include <cmath>
  6 
  7 using namespace std;
  8 
  9 #define MAXN 32
 10 __int64 sum[MAXN];//sum[i]长度i的数有多少个满足
 11 __int64 ans;
 12 
 13 __int64 C(__int64 n,__int64 m)
 14 {
 15     __int64 c=1;
 16     if(n-m<m) m=n-m;
 17     for(int i=0;i<m;i++)
 18         c=c*(n-i)/(i+1);
 19     return c;
 20 }
 21 
 22 void init()
 23 {
 24     sum[0]=0;sum[1]=0;//不包括0
 25     for(int x=2;x<MAXN;x++)
 26     {
 27         sum[x]=0;
 28         if((x-1)%2)
 29             for(int i=(x/2);i<=(x-1);i++)
 30                 sum[x]+=C(x-1,i);
 31         else
 32             for(int i=(x/2)+1;i<=(x-1);i++)
 33                 sum[x]+=C(x-1,i);
 34     }
 35 }
 36 int num[MAXN];
 37 int getlen(int x)
 38 {
 39     int len=0;
 40     memset(num,-1,sizeof(num));
 41     if(x==0)
 42     {
 43         num[0]=0;
 44         return 1;
 45     }
 46     while(x)
 47     {
 48         num[len++]=x%2;
 49         x/=2;
 50     }
 51     //for(int i=0;i<len;i++)
 52     //        cout<<num[i];
 53 //    cout<<endl;
 54     for(int i=0;i<(len/2);i++)
 55     {
 56         int t=num[i];
 57         num[i]=num[len-1-i];
 58         num[len-1-i]=t;
 59     }
 60     return len;
 61 }
 62 
 63 int  main()
 64 {
 65     int st,en;
 66     init();
 67     while(~scanf("%d%d",&st,&en))
 68     {
 69         ans=0;
 70         int len=getlen(en);
 71         //for(int i=0;i<len;i++)
 72         //    cout<<num[i];
 73         //cout<<endl;
 74         for(int i=2;i<len;i++)
 75             ans+=sum[i];
 76         //cout<<ans<<endl;
 77         int zero=0;
 78         for(int i=1;i<len;i++)
 79         {
 80             if(num[i])
 81             {
 82                 int t=(len+1)/2-zero-1;
 83                 if(t<0) t=0;
 84                 for(int j=t;j<=(len-i-1);j++)
 85                     ans+=C(len-i-1,j);
 86             }
 87             else
 88                 zero++;
 89         }
 90         //cout<<ans<<endl;
 91         if(zero>=(len+1)/2)//en本身也是
 92             ans++;
 93         //cout<<ans<<endl;
 94         len=getlen(st);
 95         for(int i=2;i<len;i++)
 96             ans-=sum[i];
 97         zero=0;
 98         for(int i=1;i<len;i++)
 99         {
100             if(num[i])
101             {
102                 int t=(len+1)/2-zero-1;
103                 if(t<0) t=0;
104                 for(int j=t;j<=(len-i-1);j++)
105                     ans-=C(len-i-1,j);
106             }
107             else
108                 zero++;
109         }
110         printf("%I64d\n",ans);
111     }
112     return 0;
113 }