这个数位dp倒是没什么限制条件,只是需要在过程中把每个数字出现次数记录一下即可。记忆化返回时数学算出。框架还是套板子。
#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; typedef long long ll;
ll n, m, cnt1[], cnt2[], dp[][];
int tot, a[]; ll dfs(int pos, int state0, int limit, ll *cnt) {
if (!pos) {
cnt[] += state0;
return ;
}
if (!limit && !state0 && dp[pos][state0] != -) {
for (int i = ; i <= ; i++) {
cnt[i] += pow(, pos - ) * pos;
}
return dp[pos][state0];
} int up = limit ? a[pos] : ;
ll ret = ; for (int i = ; i <= up; ++i) {
ll tmp = dfs(pos - , state0 & (!i), limit & (i == a[pos]), cnt);
cnt[i] += tmp;
if (i == && state0) cnt[i] -= tmp;
ret += tmp;
} if (!limit) dp[pos][state0] = ret;
return ret;
} void solve(ll x, ll *cnt) {
for (tot = ; x; x /= )
a[++tot] = x % ;
dfs(tot, , , cnt);
} int main() {
memset(dp, -, sizeof dp); cin >> n >> m;
solve(m, cnt1);
solve(n - , cnt2); for (int i = ; i <= ; ++i)
printf("%lld ", cnt1[i] - cnt2[i]); return ;
}