首页 > 代码库 > POJ 3252

POJ 3252

2024-07-24 09:15:34   218人阅读

折腾了很久。

注意到，每一个数总是这样的形式的:1010101100100。。

如，当110000到111000时，我们可以看成是从110000到110111的计数。最后特判111000即可。这时，我们需要记下前三们110中1与0的个数之差，以决定后三位取0的个数。所以，不妨预处理出0,1,10,100,1000....等两数之间的ROUND数，再按上面说的按位计数即可。

#include <iostream>#include <cstdio>#include <algorithm>#define LL __int64using namespace std;LL pd[35];LL num[35];LL myc(int n,int r){	LL sum=1;	for(int i=1;i<=r;i++)	sum=sum*(LL)(n+1-i)/(LL)i;	return sum;}void initial(){	pd[0]=1; 	pd[1]=0; 	LL tmp,sum;	int r;	for(int i=2;i<=33;i++){		r=(i-1)/2+1;		tmp=myc(i-1,r);		pd[i]=tmp;		for(int j=r+1;j<=i-1;j++){			tmp=tmp*(LL)(i-1-j+1)/(LL)j;			pd[i]+=tmp;		}	}}LL how(LL as){	LL ret=0;	while(as){		ret++;		as=(as>>1);	}	return ret;}LL ABS(LL a){	return a>=0?a:-a;}LL confer(LL as,LL bt,int pos){	LL res=0;	for(LL i=0;i<bt;i++)	res+=pd[i];	LL ans=1;	LL tmp=(1LL<<(bt-2));	LL r;	for(LL i=bt-1;i>0;i--){		if(tmp&as){			ans++;		}		else ans--;		if(tmp&as){		//	if(i-1==0) continue;			if(ans-2>=0){				r=(ans-2+i-1);				if(r%2) r=r/2+1;				else r=r/2;			}			else{				r=i-1-(ans-2);				if(r%2) r=r/2+1;				else r=r/2;				r=r-ABS(ans-2);				if(r<=0) r=0;			}			LL sum=myc((int)i-1,(int)r);			res+=sum;			for(LL k=r+1;k<=i-1;k++){				sum=sum*(i-k)/k;				res+=sum;			}		}		tmp>>=1;	}	if(ans<=0&&pos==2) res++;	return res;}int main(){	initial();	LL a,b;	while(scanf("%I64d%I64d",&a,&b)!=EOF){		LL bta=how(a),btb=how(b);		bta=confer(a,bta,1);	//	cout<<bta<<endl;		btb=confer(b,btb,2);		printf("%I64d\n",btb-bta);	}	return 0;}

　　

POJ 3252


联系
我们