这道题还是关于数位DP的板子题
数位DP有一个显著的特征，就是求的东西大概率与输入关系不大，理论上一般都是数的构成规律
然后这题就是算一个\( F(A) \)的公式值，然后求\( \left [ 0 , B \right ] \)区间内\( F(x) \)不大于\( F(A) \)的数的个数
所以由数据范围很容易得到计算出最大值不会超过4600
然后我们设状态\( dp[10][4600][4600] \)表示不同\( F(A) \)取值下的第\( pos \)个位置的值总和为 \( sumx \)的 数的个数
显然会MLE
这时候可以用减法转换状态
用\( dp[10][4600] \)表示到了第\( pos \)个位置，还要凑\( sumx \)的值的数的个数
然后就可以发现一个现象，这个状态与\( F(A) \)无关的
然后就可做了
注意一个事情，就是求的是不大于\( F(A) \)的数的个数
所以最后\( sumx \ge 0 \)就是合法状态了
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int dp[][],a[];
int dfs(int pos,int limit,int state){
if(state<)
return ;
if(pos==-){
return state>=;
}
if(!limit&&dp[pos][state]!=-)
return dp[pos][state];
int mid=,up=limit?a[pos]:;
for(int i=;i<=up;i++){
if((i<<(pos))<=state)
mid+=dfs(pos-,limit&&i==a[pos],state-(i<<(pos)));
}
if(!limit)
dp[pos][state]=mid;
return mid;
}
int solve(int A,int x){
int fa=,cona=;
while(A){
fa+=((A%)<<(cona));
A/=;
cona++;
}
int con=;
memset(a,,sizeof(a));
while(x){
a[con]=x%;
x/=;
con++;
}
return dfs(con-,true,fa);
}
int main(){
int T;
memset(dp,-,sizeof(dp) );
scanf("%d",&T);
for(int i=;i<=T;i++){
int A,B;
scanf("%d %d",&A,&B);
printf("Case #%d: %d\n",i,solve(A,B));
}
return ;
}