$\huge \color{orange}{成魔之路->}$ $\huge \color{purple}{算法提高课题解}$

思路：

1. f[i][j][k] 表示共有 i 位，最高位是 j，且各位数之和取余 P 为 k 的数的个数
2. dp(n) 表示 0 ～ n 中符合条件的数的个数，last 存储前面各位数的和
3. 首先预处理，公式：f[i][j][k] += f[i-1][x][mod(k - j, P)]
4. 依次枚举每一位，只能枚举 0 ～ x - 1，res += f[i + 1][j][mod(-last, P)]
5. 处理完所有左分支后，处理右分支，即判断各位数之和 last 是否满足条件

完整代码

#include<bits/stdc++.h>

using namespace std;

const int N = 11, M = 110;

int l,r,P;
int f[N][N][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%P]++;

    //单独处理多位数
    for(int i=2;i<N;i++)    
        for(int j=0;j<=9;j++)
            for(int k=0;k<P;k++)
                for(int x=0;x<=9;x++)
                    f[i][j][k]+=f[i-1][x][mod(k-j,P)];
}

// 0 ～ n 中符合条件的数
int dp(int n)
{
    if(!n) return 1;

    vector<int> nums;
    while(n)
    {
        nums.push_back(n%10);
        n/=10;
    }

    int res=0,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,P)];

        last+=x; //加上当前数

        if(!i&&last%P==0) res++; //这个数本身就符合条件
    }

    return res;
}

int main()
{
    while(cin>>l>>r>>P)
    {
        init();
        cout<<dp(r)-dp(l-1)<<endl;
    }

    return 0;
}