最近在补全提高课所有题目的题解，宣传一下汇总的地方提高课题解补全计划

数位DP基础概念 指路：【数位DP基本概念+数位DP记忆化搜索】

题目描述

设一个数字 各数位数字之和 为 $S$

给定正整数区间 $[l, r]$ 和正整数 $n$，求该区间内满足 $S \equiv 0 \pmod n$ 的 数字个数

分析

想了解 数位DP 基础概念的，可以看一下最上面我贴的链接，这里不会对 重复内容 进行额外讲解

把求 一段区间 的问题，转化为求两个 前缀区间 的问题

本题参数 $st$ 需要记录的参数是：前几位数位的 数字之和

然后就是很简单的 套模板 了，具体详情请看代码（推荐自己写，调不过去再来看代码，就是很简单的搜索

最近虽然课业繁重，但是题解没有参水，只是数位DP实在是太简单了（指记忆化搜索

Code

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 35, M = 110;

int l, r, n;
int a[N], al;
int f[N][M];

int dp(int pos, int st, int op)
{
    if (!pos) return !(st % n);
    if (!op && ~f[pos][st]) return f[pos][st];
    int res = 0, maxx = op ? a[pos] : 9;
    for (int i = 0; i <= maxx; i ++ )
        res += dp(pos - 1, st + i, op && i == a[pos]);
    return op ? res : f[pos][st] = res;
}
int calc(int x)
{
    memset(f, -1, sizeof f); al = 0;
    for ( ; x; x /= 10) a[ ++ al] = x % 10;
    return dp(al, 0, 1);
}
int main()
{
    while (cin >> l >> r >> n)
    {
        cout << calc(r) - calc(l - 1) << endl;
    }
    return 0;
}