P2602 [ZJOI2010] 数字计数
大意
给定区间 \([a, b]\)，统计其中所有整数中，数字 \(0 \sim 9\) 分别出现的总次数。数据范围达到 $10^{12}。
思路
状态定义
使用 f[pos][sum][lim][zero] 表示记忆化状态：
pos: 当前处理到的数位下标（从高到低）。sum: 目标数字 dig 在当前路径下已经出现的次数。lim: 布尔值，表示当前位是否受到上界限制（若为 true，则当前位最大只能填到 \(a[pos]\)）。zero: 布尔值，表示当前是否处于前导零状态。
如果 zero 为 true 且当前位填了 \(0\)，则这个 \(0\) 是前导零，不计入数字 \(0\) 的出现次数，且下一位依然处于 zero 状态。
只有当 !zero（已经填过非零数字）时，填入的数字才算作有效计数。
代码
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;const int MAXN = 15;
long long f[MAXN][MAXN][2][2];
int a[MAXN], len, dig;
//f[i][j][k][l]
//pos lim sum zero
long long dp(int pos, int sum, bool lim, bool zero){if(pos == len){return sum;}if(~f[pos][sum][lim][zero]){return f[pos][sum][lim][zero];}long long ans = 0;int maxx = lim ? a[pos] : 9;for(int i = 0;i <= maxx;i ++){bool nw = zero && (i == 0);ans += dp(pos + 1, sum + ((i == dig) && !nw), lim && (i == maxx), nw);}return f[pos][sum][lim][zero] = ans;
}long long solve(long long x){memset(f, -1, sizeof(f));len = 0;while(x){a[len ++] = x % 10;x /= 10;}reverse(a, a + len);return dp(0, 0, 1, 1);
}int main(){long long a, b;cin >> a >> b;for(int i = 0;i <= 9;i ++){dig = i;cout << solve(b) - solve(a - 1) << ' ';}return 0;
}