【题目描述】
给出两个数$a,b$，求出$[a,b]$中各位数字之和能整除原数的数的个数。
【输入格式】
一行，两个整数$a$和$b$($a,b\le 10^{18}$)
【输出格式】
一个整数，表示答案
题解
数位DP的一般思想就是表示状态，然后记忆化搜索
由于整除这个操作不太好处理，而$10^{18}$以内的数的数字和是不会超过$9*18=162$的 所以可以先枚举最终的数字和
考虑子状态需要记录哪些信息以便进行记忆化搜索
假设现在枚举到的最终数字和为$m$从高到低按数位搜索
设当前枚举到数的前$k$位，数字和为$sum$，这个$k$位数模$m$余$r$。如果两个$k$位数的$sum,r$都相同，其实后面能填的数字也会是一样的，就可以进行记忆化。
举例来说，$m=20$，枚举到第3位
$163??$和$523??$
163和523模20同余，数字和也均为10
那么后两位能填的数也会一样 不需要再搜索$523??$而是只用返回$163??$的结果
枚举$m$子状态就是$dp[i][j][k]$表示枚举到前i位，数字和为j，这个i位数模m余k
最后用$1\sim r$的减掉$1\sim l-1$的即可
时间复杂度$O(162^3*数位个数)$
【代码】
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a, b, ans, ans2;
ll num[20], len, mod;
ll dp[20][200][200];
inline void getnum(ll x) {
len = 0;
while (x) {
num[++len] = x % 10;
x /= 10;
}
}
ll dfs(ll d, ll sum, ll m, ll lim) {
if (d <= 0) {
return (m == 0 && sum == mod ? 1 : 0);
}
if (!lim && ~dp[d][sum][m]) return dp[d][sum][m];
ll ret = 0, mx = lim ? num[d] : 9;
for (int i = 0; i <= mx; i++) {
ret += dfs(d-1, sum+i, (m*10+i)%mod, lim && i == mx);
}
if (!lim) dp[d][sum][m] = ret;
return ret;
}
ll work(ll x) {
if (!x) return 0;
getnum(x);
ll ret = 0;
for (int i = 1; i <= 9 * len; i++) {
mod = i;
memset(dp, -1, sizeof(dp));
ret += dfs(len, 0, 0, 1);
}
return ret;
}
int main() {
scanf("%lld %lld", &a, &b);
ans = work(a-1);
ans2 = work(b);
printf("%lld\n", ans2 - ans);
return 0;
}
|
