AcWing 1084 数字游戏 II 题解（实体规划—DP—数位DP）
#include<bits/stdc++.h>
using namespace std;
const int N = 11, M = 110;
int P;
int f[N][10][M];//f[i][j][k]表示i位数字，最高位为j，mod N 为 k 的数字的个数
int mod(int x, int y){
return (x % y + y) % y;
}
void init(){
memset(f, 0, sizeof(f));//因为有多组测试样例，所以每次调用f需要初始化为0
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 ++ ){//mod N 的余数
for(int x = 0; x <= 9; x ++ ){//j-1位数字
f[i][j][k] += f[i - 1][x][mod(k - j, P)];
/*
位数为i，最高位为j，mod N 余数为k的数的个数等于
所有
位数为i - 1，最高位为x,mod N 余数为k-j的数字个数之和
*/
}
}
}
}
}
int dp(int n){
if(!n) return 1;
vector<int>num;
while(n) num.push_back(n % 10), n /= 10;
int res = 0;
int 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][mod(-last, P)];
/*
last 为前i-1位数字之和
所有i+1位，最高位为j，mod N (余数+last)mod N ==0的数都符合
*/
}
last += x;//last加上第i位数字
if(!i && last % P == 0) res ++ ;//如果所有位都已遍历完，且所有位数上的数字之和mod N 为0，方案数++
}
return res;
}
int main()
{
int l, r;
while(cin>>l>>r>>P){
init();
cout<<dp(r) - dp(l - 1)<<endl;
}
return 0;
}