数位dp 各个数字的和是某数的整数

#include <iostream>//数字游戏 各个数字和 取模为0
#include <vector>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;
const int N = 15,M=110;//模数范围最大到100
int P;
int f[N][10][M];//一共有i个数位 最高位数字是j   模数是k 的方案数
int get_mod(int a,int p)
{
    return (a%p+p)%p;
}
void init()//初始化太优秀了我草
{
    memset(f,0,sizeof f);//多组测试数据
    for(int i=0;i<=9;i++)
    f[1][i][i%P]=1;

    for(int i=2;i<N;i++)
    for(int j=0;j<=9;j++)//最高位的数字 
    for(int k=0;k<P;k++)//余数从0--N-1都可以
    for(int x=0;x<=9;x++)
    f[i][j][k]+=f[i-1][x][get_mod(k-j,P)];//一共i位选了j数字 然后一共
    //i-1位 选了x数字 呢么 应该 j+x+一坨%P==0  f[i-1][x][k-j%P] 就是方案数
}

int dp(int n)
{
    if(!n) return 1;
    vector<int>nums;
    int res=0;
    int last=0;//前面各个数字的和
    while(n) nums.push_back(n%10),n/=10;
    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][get_mod(-last,P)];
        last+=x;//这里是转移到右边了
        if(!i&&last%P==0) res++; 
    }

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