数字游戏2

题目描述

#10166. 「一本通 5.3 练习 1」数字游戏 - 题目 - LibreOJ (loj.ac) 由于科协里最近真的很流行数字游戏，某人又命名了一种取模数，这种数字必须满足各位数字之和 $\mathrm{mod}N$ 为 $0$。现在大家又要玩游戏了，指定一个整数闭区间 $[a,b]$，问这个区间内有多少个取模数。

输入格式

题目有多组测试数据。每组只含三个数字 $a,b,N$。

输出格式

对于每个测试数据输出一行，表示各位数字和 $\mathrm{mod}N$ 为 $0$ 的数的个数。

样例

输入

1 19 9

输出

2

数据范围与提示

对于全部数据，$1\le a,b\le 2^{31}-1,1\le N<100$。

思路

显然是数位DP。 之前通常定义状态为长度和最高位值, 这次既然是求总和为N的各位数字之和, 那么就定义为长度和各位数字和。 假如确定前一位为An-1, 当前位为x An-1 x … … … … … … 要满足的式子为 [An-1 + x + ( ... )] % N = 0 也就是说后面n-2位随意填的情况下, 有多少种情况满足 (...) % N = [ -(An-1 + x) ] % N

因此状态表示为f[i][j][k] 共i位, 最高位为j, 各数字和取模N的余数为k的方案数 状态计算：f[i][j][k] += f[i-1][q][(k - j)%N]

代码

const int N = 33, M = 110;
int f[N][10][M];
int m;
 
int mod(int x, int y)
{
    return (x % y + y) % y;
}
 
void init()
{
    memset(f, 0, sizeof f);
    for (int i = 0; i <= 9; i++)
        f[1][i][i % m]++;
 
    for (int i = 2; i < N; i++)
        for (int j = 0; j <= 9; j++)
            for (int k = 0; k < m; k++)
                for (int x = 0; x <= 9; x++)
                    f[i][j][k] += f[i - 1][x][mod(k - j, m)];
}
 
int dp(int n)
{
    if (!n)
        return 1;
 
    vector<int> nums;
    while (n)
        nums.push_back(n % 10), n /= 10;
 
    int res = 0;
    int last = 0; // 存上个数的总和
    for (int i = nums.size() - 1; i >= 0; i--)
    {
        int x = nums[i];
        for (int j = 0; j < x; j++)
            res += f[i + 1][j][mod(-last, m)];
 
        last += x;
 
        if (!i && last % m == 0)
            res++;
    }
 
    return res;
}
 
int main()
{
 
    int a, b;
    while (cin >> a >> b >> m)
    {
        init();
        cout << dp(b) - dp(a - 1) << endl;
    }
    return 0;
}