D. The Maths Lecture
time limit per test
memory limit per test
input
output
Amr doesn't like Maths as he finds it really boring, so he usually sleeps in Maths lectures. But one day the teacher suspected that Amr is sleeping and asked him a question to make sure he wasn't.
First he gave Amr two positive integers n and k. Then he asked Amr, how many integer numbers x > 0
- Decimal representation of x (without leading zeroes) consists of exactly n
- There exists some integer y > 0
- ;
- decimal representation of y is a suffix of decimal representation of x.
As the answer to this question may be pretty huge the teacher asked Amr to output only its remainder modulo a number m.
Can you help Amr escape this embarrassing situation?
Input
Input consists of three integers n, k, m (1 ≤ n ≤ 1000, 1 ≤ k ≤ 100, 1 ≤ m ≤ 109).
Output
Print the required number modulo m.
Examples
input
1 2 1000
output
4
input
2 2 1000
output
45
input
5 3 1103
output
590
Note
A suffix of a string S is a non-empty string that can be obtained by removing some number (possibly, zero) of first characters from S.
用dp[i][j]表示i位数中有多少个数MOD K 等于 j(j != 0),dp[i][0]表示i位数中有多少个数的后缀MOD %k == 0
#include <bits/stdc++.h>
#define maxn 200005
#define MOD 1000000007
using namespace std;
typedef long long ll;
ll dp[1005][105];
ll d[1005];
int main(){
//freopen("in.txt", "r", stdin);
int n, k;
ll m;
scanf("%d%d%I64d", &n, &k, &m);
d[1] = 1;
for(int i = 2; i <= n; i++)
(d[i] = d[i-1] * 10) %= k;
for(int i = 1; i <= 9; i++){
(dp[1][i%k] += 1) %= m;
}
for(int i = 2; i <= n; i++){
for(int j = 0; j <= 9; j++){
if(j)
(dp[i][d[i]*j%k] += 1) %= m;
for(int h = 0; h < k; h++){
if(h == 0){
(dp[i][0] += dp[i-1][h]) %= m;
}
else{
(dp[i][(d[i]*j+h)%k] += dp[i-1][h]) %= m;
}
}
}
}
ll ans = (dp[n][0] - dp[n-1][0] + m) % m;
printf("%I64d\n", ans);
return 0;
}