Submission #6570994


Source Code Expand

Copy
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(ll i = 0;i<((ll)(n));i++)
#define reg(i,a,b) for(ll i = ((ll)(a));i<=((ll)(b));i++)
#define irep(i,n) for(ll i = ((ll)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(ll i = ((ll)(b));i>=((ll)(a));i--)

/*
*/

template<int MOD>
struct ModInt {
	static const int Mod = MOD;
	unsigned x;
	ModInt() : x(0) { }
	ModInt(signed sig) { int sigt = sig % MOD; if (sigt < 0) sigt += MOD; x = sigt; }
	ModInt(signed long long sig) { int sigt = sig % MOD; if (sigt < 0) sigt += MOD; x = sigt; }
	int get() const { return (int)x; }

	ModInt &operator+=(ModInt that) { if ((x += that.x) >= MOD) x -= MOD; return *this; }
	ModInt &operator-=(ModInt that) { if ((x += MOD - that.x) >= MOD) x -= MOD; return *this; }
	ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MOD; return *this; }
	ModInt &operator/=(ModInt that) { return *this *= that.inverse(); }

	ModInt operator+(ModInt that) const { return ModInt(*this) += that; }
	ModInt operator-(ModInt that) const { return ModInt(*this) -= that; }
	ModInt operator*(ModInt that) const { return ModInt(*this) *= that; }
	ModInt operator/(ModInt that) const { return ModInt(*this) /= that; }

	ModInt inverse() const {
		signed a = x, b = MOD, u = 1, v = 0;
		while (b) {
			signed t = a / b;
			a -= t * b; std::swap(a, b);
			u -= t * v; std::swap(u, v);
		}
		if (u < 0) u += Mod;
		ModInt res; res.x = (unsigned)u;
		return res;
	}
};
typedef ModInt<1000000007> mint;

string s;
ll n;
mint dp[13],dp2[13];

void init(){
	cin>>s;
	n=s.size();
	dp[0]=1;
}

int main(void){
	init();
	rep(i,n){
		// cerr<<s[i]<<endl;
		if(s[i]=='?'){
			// cerr<<"???"<<endl;
			rep(j,13){
				rep(k,10)dp2[(j*10+k)%13]+=dp[j];
			}
		}else{
			int k = s[i]-'0';
			// cerr<<"k:"<<k<<endl;
			rep(j,13){
				dp2[(j*10+k)%13]+=dp[j];
			}
		}
		rep(j,13){
			dp[j]=dp2[j];
			dp2[j]=0;
		}
	}
	cout<<dp[5].get()<<endl;
	return 0;
}

Submission Info

Submission Time
Task D - Digits Parade
User RMQ
Language C++14 (GCC 5.4.1)
Score 400
Code Size 2026 Byte
Status AC
Exec Time 39 ms
Memory 512 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 16 ms 384 KB
sub1_02.txt AC 22 ms 384 KB
sub1_03.txt AC 1 ms 256 KB
sub1_04.txt AC 1 ms 256 KB
sub1_05.txt AC 18 ms 384 KB
sub1_06.txt AC 1 ms 256 KB
sub1_07.txt AC 1 ms 256 KB
sub1_08.txt AC 10 ms 512 KB
sub1_09.txt AC 38 ms 512 KB
sub1_10.txt AC 28 ms 384 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 33 ms 512 KB
sub1_18.txt AC 19 ms 512 KB
sub1_19.txt AC 38 ms 512 KB
sub1_20.txt AC 39 ms 512 KB
sub1_21.txt AC 8 ms 512 KB
sub1_22.txt AC 8 ms 512 KB
sub1_23.txt AC 8 ms 512 KB
sub1_24.txt AC 38 ms 512 KB
sub1_25.txt AC 1 ms 256 KB
sub1_26.txt AC 1 ms 256 KB