CFR 507 D. The Maths Lecture ( DP )

Problem - D - Codeforces

題意：
求長度為 N 且沒有領導 0 的正整數中，有多少數字存在一個非 0 的後綴 y，使得 k 整除 y。輸出方案術對 m 取模。

資料規模：
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，此時的方案數
特別的，為了避免重複計算，一旦偵測到有領導 0 則立刻結算，並在更新出去之前從 dp 表刪除那些方案數。

時間 / 空間複雜度：
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;
}