zkx06111's Blog

//史上写过最长的代码之一。。。80分，dfsp部分仍存在细节问题，不改了
//思路如下：求好数的个数只要求出不是好数的个数，
//求0-n不是好数只要连续1或0的个数小于等于2并且比n小就可以了
//这样就可以剪枝，大幅提高效率
#include <iostream>
#include <cstdio>
#define len(x) x[0]
using namespace std;

int mx[33];
long long low,up,ugl,ugu;

void dfs(int t,int lx,int ls){
	if (t==len(mx)){
		++ugu;
		return;
	}
	++ugu;
	if (lx==2 && ls==1){
		dfs(t+1,1,0);
		return;
	}
	if (lx==2 && ls==0){
		dfs(t+1,1,1);
		return;
	}
	if (ls==1){
		dfs(t+1,2,1);
		dfs(t+1,1,0);
		return;
	}
	dfs(t+1,1,1);
	dfs(t+1,2,0);
}

void dfsp(int t,int lx,int ls,bool flag){
	if (t>len(mx)){
		++ugu;
		return;
	}
	if (flag){
		if (ls==0 && lx==2){
			
			if (mx[t]==0) return;
			else{
				dfsp(t+1,1,1,1);
				return;
			}
		}
		if (ls==1 && lx==2){
			if (mx[t]==1){
				dfsp(t+1,1,0,0);
				return;
			}
			dfsp(t+1,1,0,1);
			return;
		}
		if (mx[t]==1){
			if (ls==0) dfsp(t+1,2,0,0);
			else{
				dfsp(t+1,2,1,1);
				dfsp(t+1,1,1,0);
			}
			return;
		}
		if (ls==0){
			dfsp(t+1,2,0,1);
			return;
		}
		dfsp(t+1,1,0,1);
		return;
	}
	if (ls==0 && lx==2){
		dfsp(t+1,1,1,0);
		return;
	}
	if (ls==1 && lx==2){
		dfsp(t+1,1,0,0);
		return;
	}
	if (ls==0){
		dfsp(t+1,1,1,0);
		dfsp(t+1,2,0,0);
		return;
	}
	dfsp(t+1,2,1,0);
	dfsp(t+1,1,0,0);
}

void conv(int x){
	len(mx)=0;
	while (x){
		mx[++len(mx)]=x%2;
		x/=2;
	}
	for (int i=1;i<=len(mx)/2;++i)
		swap(mx[i],mx[len(mx)-i+1]);
}

int main()
{
	cin>>low>>up;
	if (low<=5){
		ugl=low+1;
		goto u;
	}
	conv(low); good[1]=1;
	dfs(2,1,1);
	dfsp(2,1,1,1);
	ugl=ugu+1;
	for (int i=1;i<=len(mx)-2;++i)
		if (mx[i]==mx[i+1] && mx[i+2]==mx[i]){
			++ugl;break;}
	
	u:
	if (up<=5){
		ugu=up+1;
		goto l;
	}
	
	ugu=1;
	conv(up);
	dfs(2,1,1);
	dfsp(2,1,1,1);
	
	l:
	cout<<up-ugu-low+ugl;
	return 0;
}