[AtCoder] ABC 135 D – Digits Parade

2019年7月28日

問題

方針

動的計画法

\( d(i, j) \) を \( i \) 桁目までの調べた時、余りが \( j \) となるものの個数とします。初期値として、\( d(0, 0) = 1 \) とします。

• \( S_i = ?\) のとき

\( ? \) には、\( 0 \) から \( 9 \) までの数字が入るので、

\[ d(i + 1, (10^i \times k + j )\bmod 13) \mathrel{+}=  d[i][j] \ ( 0 \leq k \leq 9 \wedge 0 \leq j \leq 12)\]

となります。

• \( S_i = a \ ( 0 \leq a \leq 9)\) のとき

\[ d(i + 1, (10^i \times a + j )\bmod 13) \mathrel{+}=  d[i][j] \ ( 0 \leq j \leq 12)\]

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
  string S;
  cin >> S;
  ll mod = pow(10, 9) + 7;
  int l = S.length();
  ll dp[l + 1][13]{};
  dp[0][0] = 1;
  ll digit = 1;
  for (int i = l - 1; i >= 0; i--) {
    int idx = l - i;
    if (S[i] != '?') {
      ll k = S[i] - '0';
      for (ll j = 0; j < 13; j++) {
        ll m = ((digit * k )% 13 + j) % 13;
        dp[idx][m] += dp[idx - 1][j];
      }
    } else { 
      for (ll j = 0; j < 13; j++) {
        for (ll k = 0; k < 10; k++) {
          ll m = ((digit * k) % 13+ j) % 13;
          dp[idx][m] += dp[idx - 1][j];
        }
      }
    }
    for (int j = 0; j < 13; j++) {
      dp[idx][j] %= mod;
    }
    digit *= 10ll;
    digit %= 13;
  }
  cout << dp[l][5] << "\n";
  return 0;
}