Submission #4066141
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;
const int LEN = 300;
const int SQRT = 24;
int calc(int x) {
return x * (x + 1) / 2;
}
// (252, 252, 24, 100)
int dp[2][LEN][SQRT][100];
signed main() {
int N, X; cin >> N >> X;
string s; cin >> s;
s += "0"; N++;
dp[0][0][0][0] = 1;
for(int i=0; i<N; i++) {
int cur = i % 2, nxt = 1 - cur;
for(int j=0; j<=X; j++) {
for(int k=0; k<=SQRT; k++) {
for(int d=0; d<100; d++) {
if(dp[cur][j][k][d] == 0) continue;
for(int x=0; x<10; x++) {
if(s[i] != '?' and s[i] - '0' != x) continue;
int nd = (d * 10 + x) % 100, nj = j, nk = k;
if(nd == 25) nk = max(nk + 1, SQRT);
else if(nd != 52) nj = min(X, j + calc(k)), nk = 0;
(dp[nxt][nj][nk][nd] += dp[cur][j][k][d]) %= MOD;
}
dp[cur][j][k][d] = 0;
}
}
}
}
int ans = 0;
for(int i=0; i<100; 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 |
0 |
Code Size |
2167 Byte |
Status |
RE |
Exec Time |
104 ms |
Memory |
4352 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 |
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 |
RE |
101 ms |
2304 KB |
sample_02.txt |
RE |
101 ms |
2304 KB |
subtask1_01.txt |
RE |
101 ms |
2304 KB |
subtask1_02.txt |
RE |
101 ms |
2304 KB |
subtask1_03.txt |
RE |
102 ms |
2304 KB |
subtask1_04.txt |
RE |
101 ms |
2304 KB |
subtask1_05.txt |
RE |
101 ms |
2304 KB |
subtask1_06.txt |
RE |
101 ms |
4352 KB |
subtask1_07.txt |
RE |
102 ms |
4352 KB |
subtask1_08.txt |
RE |
101 ms |
4352 KB |
subtask1_09.txt |
RE |
101 ms |
4352 KB |
subtask1_10.txt |
RE |
103 ms |
4352 KB |
subtask1_11.txt |
RE |
101 ms |
2304 KB |
subtask1_12.txt |
RE |
104 ms |
2304 KB |
subtask1_13.txt |
RE |
101 ms |
2304 KB |
subtask1_14.txt |
RE |
101 ms |
2304 KB |
subtask1_15.txt |
RE |
102 ms |
2304 KB |
subtask1_16.txt |
RE |
101 ms |
2304 KB |
subtask1_17.txt |
RE |
100 ms |
2304 KB |
subtask1_18.txt |
RE |
101 ms |
2304 KB |
subtask1_19.txt |
RE |
102 ms |
2304 KB |
subtask1_20.txt |
RE |
102 ms |
2304 KB |
subtask1_21.txt |
RE |
100 ms |
2304 KB |
subtask1_22.txt |
RE |
101 ms |
2304 KB |