数位dp求调
查看原帖
数位dp求调
754856
_zexal_楼主2023/2/4 10:48
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int Maxn=64;
int n,m,len,pos[Maxn],len1,f[Maxn][2][2][Maxn][Maxn][2];
inline int dfs(int len,bool flag,int l,int tmp,int tmp2,bool fa){
	if(len==0){
		if(tmp2>=tmp) return 1;
		else return 0;
	}
	if(f[len][flag][l][tmp][tmp2][fa]!=-1) return f[len][flag][l][tmp][tmp2][fa];
	int ans=0;
	for(int i=0;i<=1;i++){
		if((i<=pos[len]||!flag)&&(!fa)) ans+=dfs(len-1,flag&&(i==pos[len]),i,tmp+i,tmp2+(i==0),fa);
		else if((i<=pos[len]||flag)&&fa) ans+=dfs(len-1,flag&&(i==pos[len]),i,tmp+i,tmp2,fa&&(i==1)); 
	}
	f[len][flag][l][tmp][tmp2][fa]=ans;	
	return ans;
}
inline int Slove(int T){
	len1=0;
	memset(f,-1,sizeof f);
	while(T){
		pos[++len1]=T&1;
		T>>=1;
	}
	return dfs(len1,1,1,0,0,1);//第 i 位,是否贴着上界,1的个数  0的个数 有没有前导零 
}
signed main(){
	cin>>n>>m;
	cout<<Slove(m)-Slove(n-1);
	return 0;
}
2023/2/4 10:48
加载中...