Submission #6582449


Source Code Expand

Copy
/* بِسْمِ اللَّهِ الرَّحْمَٰنِ الرَّحِيمِ */
//codeforces1196E
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define FASTIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define mp make_pair
#define pb push_back
void parseArray(ll* A,ll n){ for ( ll K = 0; K < n; K++){ cin >> A[K]; } }
ll modInverse(ll a, ll b){ return 1<a ? b - modInverse(b%a,a)*b/a : 1; }
ll gcd(ll a, ll b){ return b?gcd(b, a % b):a; }
ll lcm(ll a, ll b){ return (a*b)/gcd(a, b); }
ld dist(ll x, ll y, ll a, ll b){ return sqrt((x - a)*(x - a) + (y - b)*(y - b)); }
void debug(bool* a, ll n) { for ( int k = 0; k < n; k++ ){ cout << a[k] << " ";} cerr << "\n"; }

const ll mod = 1000000007;

int main(){
	FASTIO;
	string s; cin >> s;
	ll n = s.length();
	ll dp[n][13]; memset(dp, 0, sizeof dp);
	if (s[0] == '?') {
		for ( int k = 0; k < 10; k++ ){ dp[0][k] = 1; }
	}else dp[0][s[0] - '0'] = 1;
	for ( int k = 1; k < n; k++ ){
		ll temp = s[k] - '0';
		if (s[k] == '?') {
			for ( int i = 0; i < 10; i++ ){
				temp = i;
				for ( int j = 0; j < 13; j++ ){
					dp[k][(j * 10 + temp)%13] += dp[k - 1][j];
					dp[k][(j * 10 + temp)%13] %= mod;
				}
			}
		}else {
			for ( int j = 0; j < 13; j++ ){
				dp[k][(j * 10 + temp)%13] += dp[k - 1][j];
				dp[k][(j * 10 + temp)%13] %= mod;
			}
		}
	}
	cout << dp[n - 1][5] << endl;
	return 0;
}

Submission Info

Submission Time
Task D - Digits Parade
User Maaddy
Language C++14 (GCC 5.4.1)
Score 400
Code Size 1474 Byte
Status AC
Exec Time 48 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 4352 KB
sub1_02.txt AC 20 ms 6144 KB
sub1_03.txt AC 1 ms 256 KB
sub1_04.txt AC 1 ms 256 KB
sub1_05.txt AC 16 ms 5120 KB
sub1_06.txt AC 1 ms 384 KB
sub1_07.txt AC 1 ms 512 KB
sub1_08.txt AC 9 ms 8832 KB
sub1_09.txt AC 39 ms 8960 KB
sub1_10.txt AC 26 ms 6144 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 48 ms 10576 KB
sub1_18.txt AC 18 ms 10576 KB
sub1_19.txt AC 33 ms 10704 KB
sub1_20.txt AC 34 ms 10576 KB
sub1_21.txt AC 8 ms 10576 KB
sub1_22.txt AC 8 ms 10576 KB
sub1_23.txt AC 9 ms 10576 KB
sub1_24.txt AC 33 ms 10576 KB
sub1_25.txt AC 1 ms 256 KB
sub1_26.txt AC 1 ms 256 KB