Submission #4066092
Source Code Expand
// #define _GLIBCXX_DEBUG // for STL debug (optional)
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define int long long int
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
typedef pair<int, int> pii;
typedef long long ll;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const ll INF = 1001001001001001LL;
const ll MOD = 1000000007LL;
int calc(int l) {
return l * (l + 1) / 2;
}
// (idx, 通り数, 2525 文字列の長さみたいなやつ, 状態)
// 0: 何もマッチしてない
// 1: '2' までマッチ
// 2: '5' までマッチ
const int LEN = 310;
int dp[2][LEN][LEN][3], N, X;
void update(int cur, int j, int k, int l, int x) {
int nj = 0, nk = 0, nl = 0;
if(l == 2) {
if(x != 2) {
nj = min(X, j + calc(k));
nk = 0;
nl = 0;
}
else {
nj = j;
nk = k;
nl = 1;
}
}
else if(l == 1) {
if(x != 5) {
nj = min(X, j + calc(k));
nk = 0;
nl = (x == 2 ? 1 : 0);
}
else {
nj = j;
nk = k + 1;
nl = 2;
}
}
else if(l == 0) {
assert(k == 0);
nj = j, nk = k;
nl = (x == 2 ? 1 : 0);
}
int nxt = 1 - cur;
(dp[nxt][nj][nk][nl] += dp[cur][j][k][l]) %= MOD;
}
signed main() {
cin >> N >> X;
string s; cin >> s;
s += "0"; N++;
dp[0][0][0][0] = 1;
for(int i=0; i<=N; i++) {
for(int j=0; j<=X; j++) {
for(int k=0; k<=N; k++) {
for(int l=0; l<3; l++) {
int cur = i % 2, nxt = 1 - cur;
if(dp[cur][j][k][l] == 0) continue;
// fprintf(stderr, "dp[%lld][%lld][%lld][%lld] = %lld\n", i, j, k, l, dp[cur][j][k][l]);
if(i == N) continue;
if(s[i] == '?') {
for(int x=0; x<10; x++) {
update(cur, j, k, l, x);
}
}
else {
int c = s[i] - '0';
update(cur, j, k, l, c);
}
dp[cur][j][k][l] = 0;
}
}
}
}
int ans = 0;
for(int i=0; i<3; i++) (ans += dp[N%2][X][0][i]) %= MOD;
cout << ans << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
A - ニコニコ文字列2 |
User |
tsutaj |
Language |
C++14 (GCC 5.4.1) |
Score |
20 |
Code Size |
3133 Byte |
Status |
AC |
Exec Time |
414 ms |
Memory |
3968 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 |
sample_01.txt, sample_02.txt, 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 |
2 ms |
2304 KB |
sample_02.txt |
AC |
2 ms |
2304 KB |
subtask1_01.txt |
AC |
2 ms |
2304 KB |
subtask1_02.txt |
AC |
2 ms |
2304 KB |
subtask1_03.txt |
AC |
2 ms |
2304 KB |
subtask1_04.txt |
AC |
2 ms |
2304 KB |
subtask1_05.txt |
AC |
2 ms |
2304 KB |
subtask1_06.txt |
AC |
6 ms |
2560 KB |
subtask1_07.txt |
AC |
4 ms |
2432 KB |
subtask1_08.txt |
AC |
13 ms |
3200 KB |
subtask1_09.txt |
AC |
5 ms |
2560 KB |
subtask1_10.txt |
AC |
2 ms |
2560 KB |
subtask1_11.txt |
AC |
4 ms |
2304 KB |
subtask1_12.txt |
AC |
44 ms |
2432 KB |
subtask1_13.txt |
AC |
4 ms |
2304 KB |
subtask1_14.txt |
AC |
46 ms |
2944 KB |
subtask1_15.txt |
AC |
69 ms |
3968 KB |
subtask1_16.txt |
AC |
69 ms |
3840 KB |
subtask1_17.txt |
AC |
414 ms |
3968 KB |
subtask1_18.txt |
AC |
44 ms |
2304 KB |
subtask1_19.txt |
AC |
162 ms |
3584 KB |
subtask1_20.txt |
AC |
72 ms |
3712 KB |
subtask1_21.txt |
AC |
4 ms |
2304 KB |
subtask1_22.txt |
AC |
2 ms |
2304 KB |