首页 > 代码库 > POJ3252 RoundNumbers 【组合数学】
POJ3252 RoundNumbers 【组合数学】
大致题意:
给定left,right,求出[left,right]中有多少数满足如下的性质:化成二进制形式后,0的个数大于等于1
组合数学,各种小边界处理很蛋疼
大致思路是
以10101100为例子,先求[0,10000000)中满足条件的数(想想该怎么求),然后求[100 00000,101 00000),[101 00 000,101 01 000)
[101 01 000,101 01 100)中的,全加起来
一开始思路错了
然后思路对了debug很久发现combination函数写错了。。。
#include <cstdio> #include <cstdlib> #include <iostream> #include <algorithm> #include <cstring> #include <cmath> using namespace std; long long Combination(long long n,long long r) { if(n==0) return 1; if(r>n-r) r=n-r; long long i,j,s=1; for(i=0,j=0;i<r;i++) { s*=(n-i); while(s%(r-j)==0&&(r-j)>=2) { s/=(r-j); j++; } } return s; } long long cal(long long a) { long long x=1;long long bit=1; long long ret=0; while(x<=a) { x<<=1; bit++; } bit--;x>>=1; // for(long long i=0;i<=bit/2;i++) // { // ret+=Combination(bit-1,i); // } for(long long i=bit-2;i>=0;i--) { for(long long j=0;j+1<=(i+1)/2 ;j++) { ret+=Combination(i,j); } } ret+=1; long long num1=1,num0=0; long long pos=bit; while(x>>=1,pos--) { if(x&a) num1++; else num0++; if(x&a) { for(long long i=pos-1;num0+1+i>=num1-1+pos-1-i && i>=0;i--) { ret+=Combination(pos-1,i); } } } return ret; } int main() { #ifndef ONLINE_JUDGE freopen("G:/1.txt","r",stdin); freopen("G:/2.txt","w",stdout); #endif long long A,B; scanf("%lld%lld",&A,&B); printf("%lld\n",cal(B+1)-cal(A)); return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。