思路：
dp[pos][pre]代表长度为pos的不大于pre的个数
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<queue> #include<set> #include<vector> #include<map> #include<stack> #include<cmath> #include<algorithm> using namespace std; const int N = 100+5; int dp[12][200000],a[20],UP; int F(int x){ int ret = 0,pos = 0; while(x){ ret += (x % 10) *(1 << pos); pos++; x /= 10; } return ret; } int dfs(int pos,int sum,bool limit){ if(pos == -1) return sum >= 0; if(sum < 0) return 0; if(!limit && dp[pos][sum] != -1) return dp[pos][sum]; int top = limit? a[pos] : 9; int ret = 0; for(int i = 0;i <= top;i++){ ret += dfs(pos-1,sum-i*(1<<pos),limit && i == top); } if(!limit) dp[pos][sum] = ret; return ret; } int solve(int x){ int pos = 0; while(x){ a[pos++] = x % 10; x /= 10; } return dfs(pos-1,UP,true); } int main(){ int k = 1; memset(dp,-1,sizeof dp); int A,B; int T; scanf("%d",&T); while(T--){ scanf("%d%d",&A,&B); UP = F(A); printf("Case #%d: %d\n",k++,solve(B)); } return 0; }