题意：找出i在0到b之间的f(i)小于等于f(a)的数的个数。
思路：数位dp。主要在于状态转移不好想。dp[i][j]表示i位数比j小的数的个数。用递归完成的话就只需要思考边界和状态转移。
边界：
dp[i][j]如果j小于0，显然是dp[i][j]=0的，如果i==0，说明就是0，显然任何数都比0大，所以dp[i][j]对于j>=0的时候dp[i][j]=1,否则dp[i][j]=0。
状态转移：
dp[i][j]+=dp[i-1][j-k*(1<<(i-1))]；
完成上述两步推导就能开始写这题了。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 5000;
ll a, b;
int num[32];
ll dp[32][maxn];
int f(ll x) {
int ans = 0, pos = 0;
while (x) {
ans += (x%10) * (1<<pos);
pos++;
x /= 10;
}
return ans;
}
ll dfs(int pos, int state, bool limit, bool lead) {
if (pos == -1) return (state >= 0);
if (state < 0) return 0;
if (!limit && !lead && ~dp[pos][state]) return dp[pos][state];
int up = (limit ? num[pos] : 9);
ll ans = 0;
for (int i = 0; i <= up; i++) {
ans += dfs(pos-1, state-i*(1<<(pos)), limit && i == num[pos], lead && i == 0);
}
if (!limit && !lead) dp[pos][state] = ans;
return ans;
}
ll solve(ll x) {
int pos = 0;
while (x) {
num[pos++] = x % 10;
x /= 10;
}
return dfs(pos-1, f(a), true, true);
}
int main() {
int T;
scanf("%d", &T);
memset(dp, -1, sizeof(dp));
for (int kase = 1; kase <= T; kase++) {
scanf("%lld%lld", &a, &b);
printf("Case #%d: %lld\n", kase, solve(b));
}
return 0;
}