题目
分析
首先观察题目描述，$x$ 能成为幸运数的条件有以下两条：
- 每一位数字都不为 $0$，各位之和为 $y$
- $x\% z = 0$
要想解决第一个条件非常简单，只需要设 $f_{i,j}$ 为当前枚举到第 $i$ 位，各数位和为 $j$ 的方案数即可。
边界条件$f_{1,(1..9)} = 1$
转移方程如下：
\[f_{i,j} = \sum_{d=1}^{9} f_{i-1,j-d}\]最终答案即为 $\sum_{i=1}^y f_{i,y}$
那第二个条件呢？
按照数位DP的传统思路，依然是要通过前一位的状态转移到下一位。
这里的模运算转移要稍微绕一点点，我们需要从模运算的人工计算方法出发。
以下我们假设要从$ 12 \% 7=5$ 转移到 $128 \% 7 =2$。
\[\begin{align} 1\\ 7\surd{}\overline{12}\\ \underline{7}\\ 5 \end{align}\]=>
\[\begin{align} 18\\ 7\surd{}\overline{128}\\ \underline{7\ \ }\\ 58\\ \underline{56}\\ 2 \end{align}\]很显然可以看到，原来的余数乘 $10$ 后再加上新加入的一位，再模运算即可转移完成。
所以最终，我们设 $f_{sum,mod}$ 表示各数位和为 $sum$ 时，模 $z$ 的余数为 $mod$ 时的方案数
边界条件 $i=1..9, f_{i,i\% z} = 1$
从$f_{i,j}$ 转移到 $f_{i+k,(10j+k) \% z}$
答案即为 $f_{y,0}$
实现
for(int i=1;i<=9;++i)f[i][i%z]=1;
for(int i=1;i<=y;++i)
for(int j=0;j<z;++j)
for(int k=1;k<=9;++k)
f[i+k][(10*j+k)%z]=(f[i+k][(10*j+k)%z]+f[i][j])%mod;
printf("%d\n",f[y][0]);