这道题还是关于数位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 
     
      #include 
      
       #include 
       
        using namespace std;int dp[10][4600],a[10];int dfs(int pos,int limit,int state){  if(state<0)    return 0;  if(pos==-1){    return state>=0;  }  if(!limit&&dp[pos][state]!=-1)    return dp[pos][state];  int mid=0,up=limit?a[pos]:9;  for(int i=0;i<=up;i++){    if((i<<(pos))<=state)      mid+=dfs(pos-1,limit&&i==a[pos],state-(i<<(pos)));  }  if(!limit)    dp[pos][state]=mid;  return mid;}int solve(int A,int x){  int fa=0,cona=0;  while(A){    fa+=((A%10)<<(cona));    A/=10;    cona++;  }  int con=0;  memset(a,0,sizeof(a));  while(x){    a[con]=x%10;    x/=10;    con++;  }  return dfs(con-1,true,fa);}int main(){  int T;  memset(dp,-1,sizeof(dp) );  scanf("%d",&T);  for(int i=1;i<=T;i++){    int A,B;    scanf("%d %d",&A,&B);    printf("Case #%d: %d\n",i,solve(A,B));  }  return 0;}