Submission #337912
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; MINT dp[256][256][256]; bool flg[256][256][256]; inline int calc(int len) { len /= 2; return (len + 1) * len / 2; } MINT solve(int pos, int len, int rest, const string &s) { if (flg[pos][len][rest]) return dp[pos][len][rest]; MINT &ret = dp[pos][len][rest]; flg[pos][len][rest] = true; ret = 0; if (calc(len) >= rest) { ret = 1; for (int i = pos; i < s.length(); i++) if (s[i] == '?') ret *= 10; return ret; } if (calc(len + s.length() - pos) < rest) return ret = 0; if (pos == s.length()) return 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); } nrest = max(0, nrest); ret += solve(pos + 1, nlen, nrest, s); } } return ret; } int main() { int n, x; cin >> n >> x; string s; cin >> s; memset(flg, 0, sizeof(flg)); 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 | 2717 Byte |
Status | CE |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:146:28: error: ‘memset’ was not declared in this scope memset(flg, 0, sizeof(flg)); ^