Submission #532197
Source Code Expand
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<cctype>
#include<climits>
#include<iostream>
#include<string>
#include<vector>
#include<map>
//#include<list>
#include<queue>
#include<deque>
#include<algorithm>
//#include<numeric>
#include<utility>
#include<complex>
//#include<memory>
#include<functional>
#include<cassert>
#include<set>
#include<stack>
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pii;
const ll MOD = 1e9+7;
const int MAXN = 255;
ll dp[MAXN][MAXN][MAXN][2];
int N, X;
string S;
ll dfs(int n, int x, int renzoku, int f2) {
if (x >= X) return 0;
if (n >= N) return 1;
ll& ret = dp[n][x][renzoku][f2];
if (ret >= 0) return ret;
ret = 0;
if (isdigit(S[n])) {
if (S[n] == '2') {
if (f2) {
ret += dfs(n+1, x, 0, 1);
} else {
ret += dfs(n+1, x, renzoku, 1);
}
ret %= MOD;
} else if (S[n] == '5') {
if (f2) {
ret += dfs(n+1, x+renzoku+1, renzoku+1, 0);
} else {
ret += dfs(n+1, x, 0, 0);
}
ret %= MOD;
} else {
ret += dfs(n+1, x, 0, 0);
ret %= MOD;
}
} else {
for (int i = 0; i < 10; i++) {
if (i == 2) {
if (f2) {
ret += dfs(n+1, x, 0, 1);
} else {
ret += dfs(n+1, x, renzoku, 1);
}
ret %= MOD;
} else if (i == 5) {
if (f2) {
ret += dfs(n+1, x+renzoku+1, renzoku+1, 0);
} else {
ret += dfs(n+1, x, 0, 0);
}
ret %= MOD;
} else {
ret += dfs(n+1, x, 0, 0);
ret %= MOD;
}
}
}
return ret;
}
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
cin >> N >> X;
cin >> S;
ll ans = 1;
for (int i = 0; i < N; i++) if (S[i] == '?') (ans *= 10) %= MOD;
memset(dp, -1, sizeof(dp));
ans = (ans+MOD-dfs(0, 0, 0, 0))%MOD;
cout << ans << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
A - ニコニコ文字列2 |
User |
mayoko |
Language |
C++11 (GCC 4.8.1) |
Score |
0 |
Code Size |
2413 Byte |
Status |
MLE |
Exec Time |
880 ms |
Memory |
260080 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 20 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample_01.txt, sample_02.txt |
All |
subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt |
Case Name |
Status |
Exec Time |
Memory |
sample_01.txt |
MLE |
535 ms |
260020 KB |
sample_02.txt |
MLE |
526 ms |
260020 KB |
subtask1_01.txt |
MLE |
522 ms |
260064 KB |
subtask1_02.txt |
MLE |
528 ms |
260020 KB |
subtask1_03.txt |
MLE |
533 ms |
260024 KB |
subtask1_04.txt |
MLE |
551 ms |
260024 KB |
subtask1_05.txt |
MLE |
572 ms |
260080 KB |
subtask1_06.txt |
MLE |
531 ms |
260064 KB |
subtask1_07.txt |
MLE |
525 ms |
260024 KB |
subtask1_08.txt |
MLE |
545 ms |
260020 KB |
subtask1_09.txt |
MLE |
529 ms |
260024 KB |
subtask1_10.txt |
MLE |
568 ms |
260020 KB |
subtask1_11.txt |
MLE |
556 ms |
260020 KB |
subtask1_12.txt |
MLE |
551 ms |
260020 KB |
subtask1_13.txt |
MLE |
530 ms |
260080 KB |
subtask1_14.txt |
MLE |
527 ms |
260024 KB |
subtask1_15.txt |
MLE |
541 ms |
260024 KB |
subtask1_16.txt |
MLE |
543 ms |
260020 KB |
subtask1_17.txt |
MLE |
880 ms |
260000 KB |
subtask1_18.txt |
MLE |
569 ms |
260076 KB |
subtask1_19.txt |
MLE |
823 ms |
260024 KB |
subtask1_20.txt |
MLE |
550 ms |
260024 KB |
subtask1_21.txt |
MLE |
552 ms |
260024 KB |
subtask1_22.txt |
MLE |
519 ms |
260064 KB |