Submission #6574624


Source Code Expand

Copy
// {{{
#include <iostream>
#include <iomanip>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <complex>
#include <vector>
#include <list>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <algorithm>
#include <numeric>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define FOR(i, a, b) for(ll i = static_cast<ll>(a); i < static_cast<ll>(b); i++)
#define FORR(i, a, b) for(ll i = static_cast<ll>(a); i >= static_cast<ll>(b); i--)
#define REP(i, n) for(ll i = 0ll; i < static_cast<ll>(n); i++)
#define REPR(i, n) for(ll i = static_cast<ll>(n); i >= 0ll; i--)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> IP;
typedef pair<ll, LP> LLP;

const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};

constexpr int INF = 100000000;
constexpr ll LINF = 10000000000000000ll;
constexpr int MOD = static_cast<int>(1e9 + 7);
constexpr double EPS = 1e-9;

static inline ll mod(ll x, ll m)
{
    ll y = x % m;
    return (y >= 0 ? y : y+m);
}

// }}}

string s;
ll dp[100001][13];

void solve()
{
    int l = s.size();
    dp[0][0] = 1;
    REP(i, l){
        if(s[i] != '?'){
            REP(j, 13){
                dp[i+1][(10*j+s[i]-'0')%13] += dp[i][j];
                dp[i+1][(10*j+s[i]-'0')%13] %= MOD;
            }
        }else{
            REP(j, 13){
                REP(k, 10){
                    dp[i+1][(10*j+k)%13] += dp[i][j];
                    dp[i+1][(10*j+k)%13] %= MOD;
                }
            }
        }
    }
    cout << dp[l][5] << endl;
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> s;
    solve();
    return 0;
}

// vim:set foldmethod=marker:

Submission Info

Submission Time
Task D - Digits Parade
User rrrccc
Language C++14 (GCC 5.4.1)
Score 400
Code Size 1956 Byte
Status AC
Exec Time 47 ms
Memory 10704 KB

Judge Result

Set Name Sample Subtask1
Score / Max Score 0 / 0 400 / 400
Status
AC × 4
AC × 30
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt
Subtask1 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 AC 1 ms 256 KB
sample_02.txt AC 1 ms 256 KB
sample_03.txt AC 1 ms 256 KB
sample_04.txt AC 1 ms 256 KB
sub1_01.txt AC 14 ms 4480 KB
sub1_02.txt AC 20 ms 6528 KB
sub1_03.txt AC 1 ms 256 KB
sub1_04.txt AC 1 ms 256 KB
sub1_05.txt AC 17 ms 6528 KB
sub1_06.txt AC 1 ms 384 KB
sub1_07.txt AC 2 ms 512 KB
sub1_08.txt AC 12 ms 8832 KB
sub1_09.txt AC 37 ms 8960 KB
sub1_10.txt AC 25 ms 6528 KB
sub1_11.txt AC 1 ms 256 KB
sub1_12.txt AC 1 ms 256 KB
sub1_13.txt AC 1 ms 256 KB
sub1_14.txt AC 1 ms 256 KB
sub1_15.txt AC 1 ms 256 KB
sub1_16.txt AC 1 ms 256 KB
sub1_17.txt AC 47 ms 10704 KB
sub1_18.txt AC 21 ms 10704 KB
sub1_19.txt AC 34 ms 10576 KB
sub1_20.txt AC 34 ms 10576 KB
sub1_21.txt AC 12 ms 10576 KB
sub1_22.txt AC 12 ms 10704 KB
sub1_23.txt AC 12 ms 10704 KB
sub1_24.txt AC 34 ms 10704 KB
sub1_25.txt AC 1 ms 256 KB
sub1_26.txt AC 1 ms 256 KB