P3833 幸运数字

考虑动态规划。

设 $f_{i,j}$ 为数字和为 $i$ 且模 $z$ 余数为 $j$ 的数的个数。

每轮操作就在原数末尾加上一个数。

易得，状态转移方程为 $f_{i+k,(j*10+k)\%z}+=f_{i,j}$ （ $1\leq k\leq 9$ ）。

边界为 $f_{0,0}=1$ 。

代码如下：

#include<iostream>
#include<cstdio>
#define mod 1000000007
using namespace std;
int y,z,f[50001][501]={1};
int main(){
	scanf("%d%d",&y,&z);
	for(int i=0;i<y;i++){
		for(int j=0;j<z;j++){
			if(!f[i][j])continue;
			int nx=f[i][j];
			for(int k=1;k<=9;k++){
				int ni=i+k;
				int nj=j*10+k;
				if(ni>y)break;
				if(nj>=z)nj%=z;
				f[ni][nj]+=nx;
				if(f[ni][nj]>=mod)f[ni][nj]-=mod;
			}
		}
	}
	printf("%d",f[y][0]);
}