Submission #532200
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 int MOD = 1e9+7;
const int MAXN = 255;
int dp[MAXN][MAXN][MAXN][2];
int N, X;
string S;
int dfs(int n, int x, int renzoku, int f2) {
if (x >= X) return 0;
if (n >= N) return 1;
int& 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 |
20 |
Code Size |
2417 Byte |
Status |
AC |
Exec Time |
610 ms |
Memory |
130748 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
20 / 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 |
AC |
293 ms |
130664 KB |
sample_02.txt |
AC |
290 ms |
130624 KB |
subtask1_01.txt |
AC |
290 ms |
130616 KB |
subtask1_02.txt |
AC |
287 ms |
130608 KB |
subtask1_03.txt |
AC |
290 ms |
130712 KB |
subtask1_04.txt |
AC |
290 ms |
130712 KB |
subtask1_05.txt |
AC |
290 ms |
130704 KB |
subtask1_06.txt |
AC |
290 ms |
130612 KB |
subtask1_07.txt |
AC |
295 ms |
130620 KB |
subtask1_08.txt |
AC |
312 ms |
130660 KB |
subtask1_09.txt |
AC |
294 ms |
130712 KB |
subtask1_10.txt |
AC |
291 ms |
130708 KB |
subtask1_11.txt |
AC |
289 ms |
130744 KB |
subtask1_12.txt |
AC |
288 ms |
130664 KB |
subtask1_13.txt |
AC |
289 ms |
130748 KB |
subtask1_14.txt |
AC |
295 ms |
130708 KB |
subtask1_15.txt |
AC |
305 ms |
130728 KB |
subtask1_16.txt |
AC |
311 ms |
130656 KB |
subtask1_17.txt |
AC |
610 ms |
130632 KB |
subtask1_18.txt |
AC |
294 ms |
130708 KB |
subtask1_19.txt |
AC |
519 ms |
130708 KB |
subtask1_20.txt |
AC |
315 ms |
130744 KB |
subtask1_21.txt |
AC |
290 ms |
130708 KB |
subtask1_22.txt |
AC |
289 ms |
130708 KB |