Submission #338425

---

Source Code Expand

#define _USE_MATH_DEFINES
#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <cfloat>
#include <climits>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <vector>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;
typedef pair<ll, int> ll_i;
typedef pair<double, int> d_i;
typedef pair<ll, ll> ll_ll;
typedef pair<double, double> d_d;
struct edge { int u, v, w; };

ll MOD = 1000000007;
ll _MOD = 1000000009;
double EPS = 1e-10;
int INF = INT_MAX / 2;

int main() {
	int N, X; cin >> N >> X;
	string S; cin >> S;
	ll ans = 1;
	vector< vector<ll> > dp(N + 1, vector<ll>(X));
	if (X > 0) dp[0][0] = 1;
	for (int i = 0; i < N; i++) {
		char c = S[i];
		ans = ans * (c == '?' ? 10 : 1) % MOD;
		vector< vector<ll> > _dp(N + 1, vector<ll>(X));
		if (c == '2' || c == '?')
			for (int k = 0; k < X; k++) {
				for (int j = 0; j + 1 <= N; j += 2)
					_dp[j + 1][k] += dp[j][k];
				for (int j = 1; j + 1 <= N; j += 2)
					_dp[1][k] += dp[j][k];
			}
		if (c == '5' || c == '?')
			for (int k = 0; k < X; k++) {
				for (int j = 0; j + 1 <= N; j += 2)
					_dp[0][k] += dp[j][k];
				for (int j = 1; j + 1 <= N; j += 2) {
					int _k = k + (j + 1) / 2;
					if (_k < X) _dp[j + 1][_k] += dp[j][k];
				}
			}
		if (c != '2' && c != '5')
			for (int j = 0; j <= N; j++)
				for (int k = 0; k < X; k++)
					_dp[0][k] += dp[j][k] * (c == '?' ? 8 : 1);
		for (int j = 0; j <= N; j++)
			for (int k = 0; k < X; k++)
				dp[j][k] = _dp[j][k] % MOD;
	}
	for (int j = 0; j <= N; j++)
		for (int k = 0; k < X; k++)
			ans -= dp[j][k];
	cout << (ans % MOD + MOD) % MOD << endl;
}

Submission Info

Judge Result