# CFR 507 D. The Maths Lecture ( DP )

Problem - D - Codeforces

Input consists of three integers n, k, m (1 ≤ n ≤ 1000, 1 ≤ k ≤ 100, 1 ≤ m ≤ 1e9).

dp[ i ][ j ][ k ] : 長度為 i，對 k 取模為 j，是否有領導 0，此時的方案數

O( NK )

```#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000;
const int MAXK = 100;

int N, K, M;

int ten_k[ MAXN + 1 ];
int ten_m[ MAXN + 1 ];
int dp[ MAXN + 1 ][ MAXK ][ 2 ];

signed main(){
ios::sync_with_stdio( 0 );
cin >> N >> K >> M;
for( int i = ten_k[ 0 ] = ten_m[ 0 ] = 1; i <= N; ++i ){
ten_k[ i ] = 1LL * ten_k[ i - 1 ] * 10 % K;
ten_m[ i ] = 1LL * ten_m[ i - 1 ] * 10 % M;
}
int ans = 0;
dp[ 0 ][ 0 ][ 0 ] = 1;
for( int i = 0; i < N; ++i ){
for( int j = 0; j < K; ++j ){
for( int k = 0; k < 2; ++k ){
if( j == 0 and k ){
( ans += 9LL * ten_m[ N - 1 - i ] * dp[ i ][ j ][ k ] % M ) %= M;
dp[ i ][ j ][ k ] = 0;
}
for( int d = 0; d < 10; ++d ){
( dp[ i + 1 ][ ( j + d * ten_k[ i ] ) % K ][ d > 0 ] += dp[ i ][ j ][ k ] ) %= M;
}
}
}
}
( ans += dp[ N ][ 0 ][ 1 ] ) %= M;
cout << ans << endl;
return 0;
}
```