题意是求区间内数字中0的个数，比如100就有两个0。
数位dp吧，dp[i][j][k], i很明显表示当前位置，j表示找到的0的个数，k表示要找的0的个数。因为数字里0的个数最多32个，所以可以枚举32种k的情况，用数位dp去找。
#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> using namespace std; #define ll long long int dig[20]; ll dp[40][40][40]; int bigcnt; ll dfs(int pos, int cnt, int flag, int lim) { if(pos == -1) return cnt == 0; if(cnt < 0) return 0; if(!flag && !lim && dp[pos][cnt][bigcnt] != -1) return dp[pos][cnt][bigcnt]; int End = lim ? dig[pos] : 9; ll ret = 0; for(int i = 0; i <= End; i++) { if(flag && !i) ret += dfs(pos - 1, bigcnt, 1, lim && (i == End)); else if(flag && i) ret += dfs(pos - 1, bigcnt, 0, lim && (i == End)); else if(!flag && i) ret += dfs(pos - 1, cnt, 0, lim && (i == End)); else if(!flag && !i) ret += dfs(pos - 1, cnt - 1, 0, lim && (i == End)); } if(!lim && !flag) dp[pos][cnt][bigcnt] = ret; return ret; } ll func(ll num) { ll ret = 0; if(num == -1) return -1; int n = 0; while(num) { dig[n++] = num % 10; num /= 10; } for(int i = 1; i <= 32; i++) { bigcnt = i; ret += i * dfs(n - 1, i, 1, 1); } return ret; } int main() { ll a, b; memset(dp, -1, sizeof(dp)); while(~scanf("%lld %lld", &a, &b)) { if(a < 0) break; printf("%lld ", func(b) - func(a - 1)); } }