0%

[AHOI2009] 同类分布

题目

题目链接

题目大意:求出 $[a, b]$ 中各位数字之和能整除自身的数的个数。$1 \le a \le b \le 10^{18}$。时限 3s。

思路

这个记忆化怎么写倒是很好想,但是如果要保存下来每次乘的结果的话最大有可能到 $10^{18}$,拿数组没法存。

没法存的话那就考虑取模吧,但是在搜的时候各位数之和也是会变化的,行不通。

然后想了半天不知道咋搞。

后来看题解,由于时限很大,考虑枚举各位数的和,在搜的时候判断是否满足条件就行了…

由于最后要判断和,就不用管前导零了。

每次总是想不到这种有些暴力的做法,怎么办呢…

代码

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
49
50
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

template <class T>
inline void read(T &x) {
x = 0;
int f = 0;
char ch = getchar();
while (!isdigit(ch)) { f |= ch == '-'; ch = getchar(); }
while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
x = f ? -x : x;
return ;
}

typedef long long LL;

LL f[30][200][200];
LL dig[30];
LL a, b, len, mod;

LL dfs(int dep, bool lim, LL s, LL sum) {
if (!dep) return (s == 0 && sum == mod);
if ((!lim) && (~f[dep][s][sum])) return f[dep][s][sum];
LL up = lim ? dig[dep] : 9, ans = 0;
for (int i = 0; i <= up; ++i) {
ans += dfs(dep - 1, lim && i == up, (s * 10 + i) % mod, sum + i);
}
if (!lim) f[dep][s][sum] = ans;
return ans;
}

LL solve(LL x) {
len = 0;
memset(dig, 0, sizeof(dig));
while (x) dig[++len] = x % 10, x /= 10;
LL s = 0;
for (mod = 1; mod <= len * 9; ++mod) {
memset(f, -1, sizeof(f));
s += dfs(len, true, 0, 0);
}
return s;
}

int main() {
read(a), read(b);
printf("%lld\n", solve(b) - solve(a - 1));
return 0;
}