Submission #6572376


Source Code Expand

Copy
#include<bits/stdc++.h>
#define FOR(i,a,b) for(long long i = (long long)(a); i < (long long)(b); i++)
#define RFOR(i,a,b) for(long long i = (long long)(a); i >= (long long)(b); i--)
#define MIN3(a,b,c) (a)<(b)?((a)<(c)?(a):(c)):((b)<(c)?(b):(c))
#define MAX(a,b) (a)>(b)?(a):(b)
#define MIN2(a,b) (a)<(b)?(a):(b)
using namespace std;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef long long ll;
#define ull unsigned long long
typedef long double ld;
typedef vector<ll> vll;
typedef pair<ll,ll> lll;
#define deb(x )     cerr << #x << " here "<< x << endl;
#define endl    "\n"
#define printCase() "Case #" << caseNum << ": "
inline bool is_palindrome(const string& s){ return std::equal(s.begin(), s.end(), s.rbegin()); }
const ll MOD = 1000000007;
const ll INF = 1e9+5;
const double eps = 1e-7;
const double PI = acos(-1.0);
#define coud(a,d) cout << fixed << showpoint << setprecision(d) << a;
inline void debug_vi(vi a) {FOR(i, 0, a.size()) cout<<a[i]<<" ";}
inline void debug_vll(vll a) {FOR(i, 0, a.size()) cout<<a[i]<<" ";}
#define ff first
#define ss second
/*----------------------------------------------------------------------*/

const int N = 1e5+5;
ll dp[N][15];
int n;
string s;

ll solve(int curr, int sofar) {
	ll &res = dp[curr][sofar];
	if(res >= 0) return res;
	res = 0;
	if(curr == n) {
		return res = (sofar == 5);
	}
	if(s[curr] == '?') {
		int tmp;
		FOR(dig, 0, 10) {
			tmp = (sofar * 10 + dig) % 13;
			res += solve(curr+1, tmp);
			res %= MOD;
		}
	} else {
		int dig = s[curr] - '0';
		sofar = (sofar * 10 + dig) % 13;
		res += solve(curr+1, sofar);
		res %= MOD;
	}
	return res % MOD;
}

int main(){
    std::ios::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);

    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    cin>>s; n = s.size();
    memset(dp, -1, sizeof(dp));
    cout<<solve(0, 0);
    return 0;
}

Submission Info

Submission Time
Task D - Digits Parade
User srv_twry
Language C++14 (GCC 5.4.1)
Score 400
Code Size 2006 Byte
Status AC
Exec Time 90 ms
Memory 18512 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 5 ms 12032 KB
sample_02.txt AC 4 ms 12032 KB
sample_03.txt AC 4 ms 12032 KB
sample_04.txt AC 5 ms 12032 KB
sub1_01.txt AC 28 ms 14592 KB
sub1_02.txt AC 38 ms 15616 KB
sub1_03.txt AC 5 ms 12032 KB
sub1_04.txt AC 4 ms 12032 KB
sub1_05.txt AC 32 ms 14976 KB
sub1_06.txt AC 5 ms 12032 KB
sub1_07.txt AC 5 ms 12160 KB
sub1_08.txt AC 22 ms 17280 KB
sub1_09.txt AC 72 ms 17408 KB
sub1_10.txt AC 50 ms 15616 KB
sub1_11.txt AC 5 ms 12032 KB
sub1_12.txt AC 5 ms 12032 KB
sub1_13.txt AC 5 ms 12032 KB
sub1_14.txt AC 5 ms 12032 KB
sub1_15.txt AC 4 ms 12032 KB
sub1_16.txt AC 4 ms 12032 KB
sub1_17.txt AC 90 ms 18512 KB
sub1_18.txt AC 37 ms 18512 KB
sub1_19.txt AC 63 ms 18512 KB
sub1_20.txt AC 63 ms 18512 KB
sub1_21.txt AC 9 ms 18512 KB
sub1_22.txt AC 9 ms 18412 KB
sub1_23.txt AC 9 ms 18512 KB
sub1_24.txt AC 63 ms 18512 KB
sub1_25.txt AC 4 ms 12032 KB
sub1_26.txt AC 4 ms 12032 KB