「BZOJ 1799」「AHOI2009」self 同类分布

Description

给定 $l$ 和 $r\ \left( 1 \leq l \leq r \leq 10^{18} \right)$,求区间 $[l,r]$ 中各位数字之和能整除原数的数的个数。

Source

[BZOJ]1799

Solution

考虑 数位DP

用 $f_{pos,sum,now}$ 表示当前到了第 $len - pos + 1$ 位,这些数位的和是 $sum$,模 $mod$ 的值为 $now$ 的数的个数。

可以枚举 所有数位的和 的值,这个值显然不会超过 $9\lg n$(这个值在每一位都是 $9$ 时最大)。我们把这个值当做模数 $mod$,当前数每增加一位时,我们统计各个数位的和 $sum$,并将新的数对 $mod$ 取模。当搜到最后一位时,如果模数为 $0$,那么满足条件整除;如果 $sum = mod$,那么满足 此时所有数位的和 = 枚举的所有数位的和 。如果上述两个条件都满足,则说明这个数符合题意。同时因为只需要统计 各个数位和 以及 数对 $mod$ 取模的值,所以不需要判前导零。具体实现过程详见代码,时间复杂度为 $O(9^3n\lg^3 n)$ 。

Code

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
51
52
53
54
55
56
57
58
59
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

template <class T>
inline void read(T &x) {
x = 0;
char c = getchar();
bool f = 0;
for (; !isdigit(c); c = getchar()) f ^= c == '-';
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
x = f ? -x : x;
}

template <class T>
inline void write(T x) {
if (x < 0) {
putchar('-');
x = -x;
}
T y = 1;
int len = 1;
for (; y <= x / 10; y *= 10) ++len;
for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}

const int MAXN = 18, MAXM = MAXN * 9;
LL l, r, f[MAXN + 5][MAXM + 5][MAXM + 5];

LL dfs(int *num, int pos, int sum, int now, int mod, bool lim) {
//pos 表示当前是第 len - pos + 1 位,sum 表示此时所有数位的和,
//now 表示当前的数对 mod 取模后的值,mod 表示枚举的所有数位的和,lim 表示当前数位是否受到限制
if (!pos) return !now && sum == mod;//如果 能够整除 且 此时所有数位的和 = 枚举的所有数位的和,返回 1
if (!lim && ~f[pos][sum][now]) return f[pos][sum][now];//返回已记录的值
LL res = 0;
int maxNum = lim ? num[pos] : 9;//当前数位最大值
for (int i = 0; i <= maxNum; ++i)
res += dfs(num, pos - 1, sum + i, (now * 10 + i) % mod, mod, lim && i == maxNum);//查找下一位
if (!lim) f[pos][sum][now] = res;//记录该状态的值
return res;
}

inline LL solve(LL x) {
int len = 0, num[MAXN + 5];
for (; x; x /= 10) num[++len] = x % 10;
LL res = 0;
for (int i = 1; i <= 9 * len; ++i) {//枚举所有数位的和,最大不会超过 9 * 数位长度(每一位都是 9)
memset(f, -1, sizeof (f));//初始化
res += dfs(num, len, 0, 0, i, 1);//设所有数位的和为 i,累加答案,且注意第一位会受限
}
return res;
}

int main() {
read(l), read(r);
write(solve(r) - solve(l - 1));
putchar('\n');
return 0;
}

本文标题:「BZOJ 1799」「AHOI2009」self 同类分布

文章作者:Heartlessly

发布时间:2019年04月22日 - 11:40:51

最后更新:2019年04月27日 - 15:44:15

原始链接:https://heartlessly.github.io/problems/bzoj-1799/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

0%