Submission #337914

---

Source Code Expand

#include <iostream>
#include <string>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <cstdio>
#include <cstdint>
#include <stack>
#include <memory.h>
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

Judge Result