这道题目有人往数学去想了……但是正解是 dp 哦~
我们来讲解 dp 的要素！
- 定义： dp[i][j] 为当数码和为 i 时，模 z 余 j 时有几个满足要求的数。
- 遍历：三层循环，第一层，枚举数码和，第二层枚举余数，第三层枚举新添加在末尾的数。
- 状态转移：设 i 为当前的数码和 j 为当前的余数 k 为要新添加的数字。那么
dp[i+k][(j\times 10+k)\ \mathrm{mod}\ z]=(dp[i+k][(j\times 10+k)\ \mathrm{mod}\ z]+dp[i][j])\ \mathrm{mod} \ 1000000007
因为我们将当数码和为 i 余数为 j 的数在末尾添加一个数 k 的时候数码和变为 i+k 余数变为 (j\times 10+k)\ \mathrm{mod}\ z 。 - 初始化： dp[0][0] 只有一种情况所以将它初始化为 1 。
- 答案： dp[y][0] 。
伪代码：
dp[0][0]=1;//初始化
for(int i=0;i<y;i++){//枚举数码和
for(int j=0;j<z;j++){//枚举余数
if(dp[i][j]==0)continue;//若没有可能直接跳过
for(int k=1;k<=9;k++){//因为没有 0 所以只能枚举 1~9
if(i+k<=y){//判断会不会超出边界
//状态转移
}
}
}
cout<<dp[y][0];//输出答案
代码时间复杂度：时间主要开销在三层循环所以时间复杂度为 O(y\times z\times 9) 。
代码空间复杂度：主要用于存储 dp 数组空间复杂度为 O(50005\times 500) 。