Submission #6616625


Source Code Expand

Copy
#include <bits/stdc++.h>

#define rep(i, a, b) for (ll i = (a); i < (b); i++)
typedef uint64_t ull;
typedef int64_t ll;
typedef std::pair<ll, ll> PLL;

using namespace std;

const ll M = 1000000007;

ll dp[100100][13]; // dp[i][j]: i桁目まで見た時に、あまりがjとなる場合の数

signed main() {
  rep(i,0,100100) rep(j,0,13) dp[i][j]=0;
  string s;
  cin>>s;
  ll N = s.size();
  reverse(begin(s),end(s));
  dp[0][0] = 1;
  for (ll i=1, ten=1; i<=N; i++,(ten*=10)%=13) {
    if (s[i-1] == '?') {
      rep(x,0,10) {
        ll m = (x*ten) % 13;
        rep(j,0,13){
          (dp[i][(j+m) % 13] += dp[i-1][j]) %= M;
        }
      }
    } else {
      ll x = s[i-1] - '0';
      ll m = (x*ten) % 13;
      rep(j,0,13){
        (dp[i][(j+m) % 13] += dp[i-1][j]) %= M;
      }
    }
  }
  cout<<dp[N][5]<<endl;
  return 0;
}

Submission Info

Submission Time
Task D - Digits Parade
User bobuhiro11
Language C++14 (GCC 5.4.1)
Score 400
Code Size 880 Byte
Status
Exec Time 53 ms
Memory 10624 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt
Subtask1 400 / 400 sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sub1_01.txt, sub1_02.txt, sub1_03.txt, sub1_04.txt, sub1_05.txt, sub1_06.txt, sub1_07.txt, sub1_08.txt, sub1_09.txt, sub1_10.txt, sub1_11.txt, sub1_12.txt, sub1_13.txt, sub1_14.txt, sub1_15.txt, sub1_16.txt, sub1_17.txt, sub1_18.txt, sub1_19.txt, sub1_20.txt, sub1_21.txt, sub1_22.txt, sub1_23.txt, sub1_24.txt, sub1_25.txt, sub1_26.txt
Case Name Status Exec Time Memory
sample_01.txt 5 ms 10368 KB
sample_02.txt 5 ms 10368 KB
sample_03.txt 5 ms 10368 KB
sample_04.txt 5 ms 10368 KB
sub1_01.txt 18 ms 10496 KB
sub1_02.txt 24 ms 10496 KB
sub1_03.txt 5 ms 10368 KB
sub1_04.txt 5 ms 10368 KB
sub1_05.txt 21 ms 10496 KB
sub1_06.txt 6 ms 10368 KB
sub1_07.txt 6 ms 10368 KB
sub1_08.txt 15 ms 10624 KB
sub1_09.txt 43 ms 10624 KB
sub1_10.txt 31 ms 10496 KB
sub1_11.txt 6 ms 10368 KB
sub1_12.txt 5 ms 10368 KB
sub1_13.txt 5 ms 10368 KB
sub1_14.txt 5 ms 10368 KB
sub1_15.txt 5 ms 10368 KB
sub1_16.txt 5 ms 10368 KB
sub1_17.txt 53 ms 10624 KB
sub1_18.txt 23 ms 10624 KB
sub1_19.txt 38 ms 10624 KB
sub1_20.txt 38 ms 10624 KB
sub1_21.txt 14 ms 10624 KB
sub1_22.txt 13 ms 10624 KB
sub1_23.txt 14 ms 10624 KB
sub1_24.txt 38 ms 10624 KB
sub1_25.txt 5 ms 10368 KB
sub1_26.txt 5 ms 10368 KB