Submission #337881
Source Code Expand
#include <iostream>
#include <string>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <cstdio>
#include <cstdint>
#include <stack>
using namespace std;
#pragma region mint
// modulo integer
// M: modulo number
// * M < 2^31
// * M must be prime if you use division
template <int64_t M>
class mint {
public:
mint():v(0) {}
mint(int n): v(n % M) {}
int64_t get() const { return v; }
mint &operator+=(const mint &r) {
v = (v + r.v) % M;
return *this;
}
mint &operator-=(const mint &r) {
v = (v - r.v + M) % M;
return *this;
}
mint &operator*=(const mint &r) {
v = (v * r.v) % M;
return *this;
}
mint &operator/=(const mint &r) {
return (*this) *= r.inv();
}
mint pow(int r) const {
mint k = *this, ret = 1;
while (r > 0) {
if (r % 2 != 0) ret *= k;
r /= 2;
k *= k;
}
return ret;
}
mint inv() const {
return pow(M - 2);
}
private:
int64_t v;
};
template <int64_t M>
inline mint<M> operator+(mint<M> l, const mint<M> &r) {
return l += r;
}
template <int64_t M>
inline mint<M> operator-(mint<M> l, const mint<M> &r) {
return l -= r;
}
template <int64_t M>
inline mint<M> operator*(mint<M> l, const mint<M> &r) {
return l *= r;
}
template <int64_t M>
inline mint<M> operator/(mint<M> l, const mint<M> &r) {
return l /= r;
}
template <int64_t M>
inline ostream &operator<<(ostream &os, const mint<M> &r) {
return os << r.get();
}
#pragma endregion
typedef mint<1000000007> MINT;
map<tuple<int, int, int>, MINT> dp;
int calc(int len) {
len /= 2;
return (len + 1) * len / 2;
}
MINT solve(int pos, int len, int rest, const string &s) {
if (rest < 0) rest = 0;
if (pos == s.length()) {
if (calc(len) >= rest)
return 1;
else
return 0;
}
tuple<int, int, int> key(pos, len, rest);
if (dp.count(key))
return dp[key];
MINT &ret = dp[key];
ret = 0;
for (int i = 0; i <= 9; i++) {
if (s[pos] == '?' ||
s[pos] == '0' + i) {
int nlen = 0;
if (len % 2 == 0 && i == 2) nlen = len + 1;
if (len % 2 == 1 && i == 5) nlen = len + 1;
if (i == 2 && nlen == 0) nlen = 1;
int nrest = rest;
if (nlen < len) {
nrest -= calc(len);
}
ret += solve(pos + 1, nlen, nrest, s);
}
}
return ret;
}
int main() {
int n, x; cin >> n >> x;
string s; cin >> s;
cout << solve(0, 0, x, s) << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
A - ニコニコ文字列2 |
User |
tanakh |
Language |
C++11 (GCC 4.8.1) |
Score |
0 |
Code Size |
2496 Byte |
Status |
TLE |
Exec Time |
2036 ms |
Memory |
59552 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 |
AC |
23 ms |
796 KB |
sample_02.txt |
AC |
23 ms |
920 KB |
subtask1_01.txt |
AC |
23 ms |
796 KB |
subtask1_02.txt |
AC |
24 ms |
924 KB |
subtask1_03.txt |
AC |
24 ms |
920 KB |
subtask1_04.txt |
AC |
25 ms |
928 KB |
subtask1_05.txt |
AC |
25 ms |
808 KB |
subtask1_06.txt |
AC |
30 ms |
1320 KB |
subtask1_07.txt |
AC |
32 ms |
1312 KB |
subtask1_08.txt |
AC |
315 ms |
7712 KB |
subtask1_09.txt |
AC |
83 ms |
2588 KB |
subtask1_10.txt |
AC |
33 ms |
1192 KB |
subtask1_11.txt |
AC |
25 ms |
1060 KB |
subtask1_12.txt |
AC |
31 ms |
1324 KB |
subtask1_13.txt |
AC |
26 ms |
932 KB |
subtask1_14.txt |
AC |
71 ms |
3096 KB |
subtask1_15.txt |
AC |
1274 ms |
59552 KB |
subtask1_16.txt |
AC |
1176 ms |
53396 KB |
subtask1_17.txt |
TLE |
2036 ms |
40612 KB |
subtask1_18.txt |
AC |
23 ms |
932 KB |
subtask1_19.txt |
TLE |
2036 ms |
41896 KB |
subtask1_20.txt |
AC |
1485 ms |
57632 KB |
subtask1_21.txt |
AC |
93 ms |
2720 KB |
subtask1_22.txt |
AC |
28 ms |
1064 KB |