POJ3252 Round Numbers（不重复全排列）

题目问区间有多少个数字的二进制0的个数大于等于1的个数。

用数学方法求出0到n区间的合法个数，然后用类似数位DP的统计思想。

我大概是这么求的，确定前缀的0和1，然后后面就是若干个0和若干个1的不重复全排列数。。

写得挺痛苦的。。另外A[i][j]表示i个0和j个1的不重复全排列数，即A[i][j]=(i+j)!/i!/j!，这个可以从A[i-1][j]或A[i][j-1]求出来，这样就不用担心乘法溢出了。

 #include<cstdio>

 #include<cstring>

 using namespace std;

 long long d[][];

 long long cnt(int zero,int one,int len){

     long long res=;

     for(int i=; i<=len; ++i){

         int j=len-i;

         if(i+zero<j+one) continue;

         res+=d[i][j];

     }

     return res;

 }

 long long calu(int a){

     int len=;

     while(len!=- && ((a>>len)&)==) --len;

     if(len==-) return ;

     long long res=;

     for(int i=; i<len; ++i){

         res+=cnt(,,i);

     }

     int zero=,one=;

     for(int i=len-; i>=; --i){

         if((a>>i)&){

             res+=cnt(zero+,one,i);

             ++one;

         }else{

             ++zero;

         }

     }

     zero=; one=;

     for(int i=; i<=len; ++i){

         if((a>>i)&) ++one;

         else ++zero;

     }

     return res+(zero>=one);

 }

 int main(){

     d[][]=;

     for(int i=; i<; ++i){

         for(int j=; j<; ++j){

             d[i+][j]=d[i][j]*(i+j+)/(i+);

             d[i][j+]=d[i][j]*(i+j+)/(j+);

         }

     }

     int a,b;

     while(~scanf("%d%d",&a,&b)){

         printf("%lld\n",calu(b)-calu(a-));

     }

     return ;

 }

巴特西

POJ3252 Round Numbers（不重复全排列）

最新文章

热门文章