传送门：点击打开链接
题意：一个长度为n的数，没有前缀0，如果这个数存在一个后缀y，这个y没有前导0且大于0，能整除k，这么就认为数x是满足要求的
问有多少个数x满足要求
思路：明显是从后往前算的数位dp。
首先我们肯定可以想到dp[i][j]表示正在考虑第i位对后面的影响，当前的数字取模k等于j
那么再枚举第i+1位是什么数字，就能往后面转移了，不过这道题有两个细节和一个trick
一个细节是最高位一定不能等于0，还有一个细节就是y必须大于0。
所以一开始的边界条件里，第一个数要从1开始考虑，而且连续出现0应该再单独拿出来考虑才行。
一个trick就是如果m=1，那么最后的答案肯定等于0，这里绝对不会出错的方法就是，在输出的时候再取模一次，万无一失~
#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<cstdio>
#include<cctype>
#include<string>
#include<vector>
#include<cstring>
#include<iomanip>
#include<iostream>
#include<algorithm>
#include<functional>
#define fuck(x) cout<<"["<<x<<"]"
#define FIN freopen("input.txt","r",stdin)
#define FOUT freopen("output.txt","w+",stdout)
using namespace std;
typedef long long LL;
typedef pair<int, int>PII;const int MX = 1e3 + 5;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;LL dp[MX][MX];
int n, m, k;void solve() {LL f = 1;memset(dp, 0, sizeof(dp));for(int i = 0; i < n; i++) {if(i == 0) {for(int x = 1; x <= 9; x++) dp[1][x % k]++;f = f * 10 % k; continue;}for(int j = 1; j < k; j++) {for(int x = 0; x <= 9; x++) {if(x == 0 && i == n - 1) continue;int id = (f * x + j) % k;dp[i + 1][id] = (dp[i + 1][id] + dp[i][j]) % m;}}for(int x = 1; x <= 9; x++) {dp[i + 1][f * x % k]++;}dp[i + 1][0] = (dp[i + 1][0] + dp[i][0] * 9) % m;if(i != n - 1) dp[i + 1][0] = (dp[i + 1][0] + dp[i][0]) % m;f = f * 10 % k;}printf("%I64d\n", dp[n][0] % m);
}int main() {//FIN;while(~scanf("%d%d%d", &n, &k, &m)) {solve();}return 0;
}