AcWing 1084. 数字游戏 II（数位dp）

题意：

定义一种取模数，这种数字必须满足 各位数字之和 mod N 为 0。

指定一个整数闭区间 [a, b]，问这个 区间内有多少个取模数。

思路：

一般来说，数位Dp这类题目难点在于 如何预处理左分支方案数

对于本题，假设我们当前枚举到的第 i 位，且第 i 位上的数字是 x，那么对于答案中的第 i 位数字 j 来说，可以填两类数：

• 1.0 ~ x - 1
  用 j 表示第 i 位数字（最高位），用 last 表示当前数严格前面数位上的数字之和，用sum表示后 i + 1 位（包括第 i 位）数字之和，
  则sum 与 last 的 关系式 为 (last + sum) % N == 0（保证各个数位总和模 N 得 0），
  将上式稍作变形，即得 sum % N 的结果 等价于 (- last) % N，答案 res 累加：res += f[i + 1][j][((- last) % N)]。

• 2.x
  如果 j 填 x，last += x，之后 枚举下一位。

接下来讨论 如何预处理 f 数组：

f[i][j][k] 状态表示：

f[i][j][k] 表示 一共有 i 位，且最高位数字是 j，且所有位数字和模 N 结果为 k 的数的个数

状态转移： 因为 第 i 位是 j，且 所有数字之和模 N 为 k，所以我们考虑 第 i - 1 位，假设 第 i - 1 位数字是 x，由于 j 已经固定，
那么 剩下的 i - 1 位数字之和模 N 的结果 即为：(k - j) % N，

推出 状态转移方程：
（mod 函数能起到防止模结果为负的情况，代码中有具体体现）

#include<bits/stdc++.h>

using namespace std;
const int N = 15, M = 110;
int mod;
int n;
int f[N][N][M];//f[i][j][k] 代表共 i 位，最高位 i 为 j，各数位总和取余为 k 的数的方案数
typedef vector<int> vi;
#define pb push_back
#define pp pop_back

void init()
{
        memset(f, 0, sizeof f);
        for(int i=0; i<=9; ++i)
        {
            int t = i % mod;
            f[1][i][t] = 1;
        }
        for(int i=2; i<N; ++i)
        {
                for(int j=0; j<=9; ++j)
                {
                        for(int k=0; k<=9; ++k)
                        {
                                for(int m=0; m<mod; ++m)
                                {
                                        f[i][j][m] += f[i-1][k][((m-j)%mod+mod)%mod];
                                }
                        }
                }
        }
}

int dp(int n)
{
        if(!n) return 1;//注意 当 n 得 0 的时候也是一个合法的方案，0 模 任何数 都得 0，为 1 种方案
        vi num; while(n) num.pb(n%10), n /= 10;
        int res = 0, last = 0;
        for(int i=num.size()-1; i>=0; --i)
        {
                int x = num[i];
                for(int j=0; j<x; ++j)//左分支
                {
                        res += f[i+1][j][((-last)%mod+mod)%mod];
                }

                last += x;//累加当前数，此为右分支
                if(!i && !(last%mod)) ++res;//添加最后的答案
        }

        return res;
}

int main()
{
        int l, r;
        while(cin>>l>>r>>mod)
        {
                init();
                cout<<dp(r) - dp(l-1)<<'\n';
        }

        return 0;
}