AK-dream

【题目描述】
给出两个数$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;
}


 评论