「UVa 11361」Investigating Div-Sum Property - 数位 DP

问在区间 内有多少数 满足：

1. 是 的倍数；
2. 的各位数之和是 的倍数。

链接

UVa 11361

题解

设 表示 的各位数之和， 表示 内有多少正整数 满足 且 ，问题转化为求 。

设 表示有多少 位数 满足 且 ，计算 函数可以枚举最高位数字 1 ~ 9，并递归计算。

函数也可以递归求，设参数 的最高位上的数为 ，则可以先在 枚举最高位上的数，此时后面的低位数是任意的，可以由 函数来计算；最后令最高位为 ，递归处理低位的数，累加起来就是答案。

题目有坑， 较大时结果直接为零 ……

代码

#include <cstdio>
#include <cstring>

const int MAXT = 99;
const int MAXX = 1 << 31;
const int MAXK = 9999;
const int MAXK_HEHE = 100;

int k, pow10[12];

long long mem[11][MAXK_HEHE + 1][MAXK_HEHE + 1];
bool calced[11][MAXK_HEHE + 1][MAXK_HEHE + 1];

inline void makeTable() {
    pow10[0] = 1;
    for (int i = 1; i <= 11; i++) pow10[i] = pow10[i - 1] * 10;
}

inline int length(int x) {
    int result = 0;
    do result++; while (x /= 10);
    return result;
}

inline int sum(int x) {
    int result = 0;
    do result += x % 10; while (x /= 10);
    return result;
}

inline int mod(int a, int b) {
    return (a % b + b) % b;
}

int f(int x, int m1, int m2) {
    long long &ans = mem[x][m1][m2];
    if (calced[x][m1][m2]) return ans;
    calced[x][m1][m2] = true;

    ans = 0;
    if (x == 1) {
        for (int i = 0; i <= 9; i++) {
            if (i % k == m1 && i % k == m2) ans++;
        }
    } else {
        for (int i = 0; i <= 9; i++) {
            ans += f(x - 1, mod(m1 - i, k), mod(m2 - i * pow10[x - 1] % k, k));
        }
    }

    // printf("f(%d, %d, %d) = %d\n", x, m1, m2, ans);
    return ans;
}

int dp(int x, int m1, int m2) {
    int ans = 0;
    if (x < 10) {
        for (int i = 0; i <= x; i++) {
            if (i % k == m1 && i % k == m2) ans++;
        }
    } else {
        int n = length(x), first = x / pow10[n - 1];
        for (int i = 0; i < first; i++) {
            ans += f(n - 1, mod(m1 - i, k), mod(m2 - pow10[n - 1] * i, k));
        }
        ans += dp(x % pow10[n - 1], mod(m1 - first, k), mod(m2 - pow10[n - 1] * first, k));
    }

    return ans;
}

/*
inline int solve(int x) {
    int n = length(x), left = 0;
    int ans = 0;
    for (int i = n - 1; i > 0; i--) {
        int curr = (x % pow10[i + 1]) / pow10[i];
        // printf("curr = %d\n", curr);
        for (int j = 0; j < curr; j++) {
            int t = left * 10 + j;
            // printf("sum(t) = %d; %d\n", sum(t), t * pow10[i - 1]);
            ans += f(i, mod(k - sum(t), k), mod(t * pow10[i] % k, k));
        }
        left = left * 10 + curr;
    }

    for (int i = 0; i <= x % 10; i++) {
        if ((x - i) % k == 0 && sum(x - i) % k == 0) ans++;
    }

    return ans;
}
*/

inline void cleanUp() {
    memset(mem, 0, sizeof(mem));
    memset(calced, 0, sizeof(calced));
}

int main() {
    makeTable();

    int t;
    scanf("%d", &t);
    for (int i = 0; i < t; i++) {
        int a, b;
        scanf("%d %d %d", &a, &b, &k);
        if (k >= 100) puts("0"); // hehe
        else printf("%d\n", dp(b, 0, 0) - dp(a - 1, 0, 0));
        cleanUp();
    }

    return 0;
}