求助数位dp
查看原帖
求助数位dp
551803
BPG_ning楼主2022/10/26 17:58
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int x,y,n,a[50],dp[50][50][2][2];
void init(int x){
	memset(dp,0,sizeof(dp));
	for(n=0;x;x>>=1) a[++n]=(x&1);
}
int sol(int x){
	init(x);
	dp[n][1][1][1]=1;
	dp[n][0][0][0]=1;
	for(int i=n-1;i>=1;i--){
		for(int j=0;j<=n-i+1;j++){
			dp[i][j][0][0]+=dp[i+1][j][0][0];
			if(j>=1) dp[i][j][0][0]+=dp[i+1][j-1][1][0];
			if(a[i]>0){
				dp[i][j][0][0]+=dp[i+1][j][0][1];
				if(j>=1)dp[i+1][j-1][1][1];
			}
			if(j>=1){
				dp[i][j][1][0]+=dp[i+1][j-1][0][0];
				if(j>=2) dp[i][j][1][0]+=dp[i+1][j-2][1][0];
				if(a[i]==1){
					dp[i][j][1][1]+=dp[i+1][j-1][0][1];
					if(j>=2)dp[i][j][1][1]+=dp[i+1][j-2][1][1];
				}
			}
		}
	}
	int sum=0;
	for(int i=0;i<=n/2;i++){
		sum+=dp[1][i][0][0]+dp[1][i][0][1]+dp[1][i][1][0];
		if(a[1]==1)sum+=dp[1][i][1][1];
	}
	return sum;
}
int main(){
	ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	cin>>x>>y;
	cout<<sol(y)-sol(x-1)<<endl; 
	return 0;
}
2022/10/26 17:58
加载中...