「Luogu P4127」「AHOI2009」同类分布

Description

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

Source

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

#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;
}