Light OJ 1068

数位DP

#include <cstdio>
#include <cstring>
using namespace std;

const int MAX_DIGIT = 15;
const int MAX_K = 10005;

long long n;
int f[MAX_DIGIT];
long long memoize[MAX_DIGIT][MAX_DIGIT * 9][MAX_DIGIT * 9];
int k;

int to_digits(long long a)
{
    int ret = 0;
    while (a > 0)
    {
        f[ret++] = a % 10;
        a /= 10;
    }
    return ret;
}

long long dfs(int digit, bool less, int sum, int remainder)
{
    if (digit < 0)
    {
        return sum == 0 && remainder == 0;
    }
    if (less && memoize[digit][sum][remainder] != -1)
    {
        return memoize[digit][sum][remainder];
    }
    int limit = less ? 9 : f[digit];
    long long ret = 0;
    for (int i = 0; i <= limit; i++)
    {
        ret += dfs(digit - 1, less || i < f[digit], (sum + i) % k, (remainder * 10 + i) % k);
    }
    if (less)
    {
        memoize[digit][sum][remainder] = ret;
    }
    return ret;
}

long long work(long long n)
{
    if (n < 0)
    {
        return 0;
    }
    if (n == 0)
    {
        return 1;
    }
    int len = to_digits(n);
    if (k >= MAX_DIGIT * 9)
    {
        return 0;
    }
    return dfs(len - 1, false, 0, 0);
}

int main()
{
    int t;
    scanf("%d", &t);
    for (int i = 1; i <= t; i++)
    {
        int a, b;
        scanf("%d%d%d", &a, &b, &k);
        memset(memoize, -1, sizeof(memoize));
        printf("Case %d: %lld
", i, work(b) - work(a - 1));
    }
    return 0;
}