Submission #4030450

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <cstring>
#include <sstream>
#include <map>
#include <queue>
#include <set>
#include <vector>
#include <stack>
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> pos;
const ll MOD = 1000000007, N = 200000, dx[4] = { -1,1,0,0 }, dy[4] = { 0,0,-1,1 };

ll mn(ll a, ll b) {
	if (a == -1)return b;
	if (b == -1)return a;
	return min(a, b);
}
ll gcd(ll v1, ll v2) {
	if (v1 == 0)return v2; if (v2 == 0)return v1; if (v2 > v1)return gcd(v2%v1, v1); return gcd(v1%v2, v2);
}
struct ab {
	ll a, b;
	bool operator<(const ab& right) const {
		return right.b*a - right.a*b < 0;
	}
};

/*
void src(ll v, ll d[]) {
priority_queue<pos> q;
q.push(make_pair(0, v));
while (!q.empty()) {
ll ci = q.top().second, cd = -q.top().first;
q.pop();
if (d[ci] != -1)continue; d[ci] = cd;
for (int i = 0; i < G[ci].size(); i++) {
ll ni = G[ci][i].second, nd = cd + G[ci][i].first;
if (d[ni] != -1)continue;
q.push(make_pair(-nd, ni));
}
}
}
*/

ll n, x, dp[254][254][254];//index x_count niconico

int main() {
	cin >> n >> x;
	dp[0][0][0] = 1;
	for (int i = 0; i < n; i++) {
		char v1; cin >> v1;
		if (v1 == '?') {
			for (ll j = 0; j <= 252; j++) {
				for (int k = 0; k <= 252; k++) {
					if (dp[i][j][k] == 0)continue;
					if (k % 2 == 1) {
						//add 5 
						dp[i + 1][min(x,j + k / 2 + 1)][k + 1] = (dp[i + 1][min(x, j + k / 2 + 1)][k + 1] + dp[i][j][k]) % MOD;
						//add 2
						dp[i + 1][j][1] = (dp[i + 1][j][1]+dp[i][j][k])%MOD;

						dp[i + 1][j][0] = (dp[i + 1][j][0] + dp[i][j][k] * 8) % MOD;
					}
					else {
						dp[i + 1][j][0] = (dp[i + 1][j][0] + dp[i][j][k]*9) % MOD;
						dp[i + 1][j][k + 1] = (dp[i + 1][j][k + 1] + dp[i][j][k]) % MOD;
					}
				}
			}
		}
		else {
			for (ll j = 0; j <= 252; j++) {
				for (int k = 0; k <= 252; k++) {
					if (dp[i][j][k] == 0)continue;
					if (k % 2 == 1 && v1 == '5') {
						dp[i + 1][min(x, j + k / 2 + 1)][k + 1] = (dp[i + 1][min(x, j + k / 2 + 1)][k + 1] + dp[i][j][k]) % MOD;
					}
					else if (v1 == '2') {
						if(k%2==0)dp[i + 1][j][k + 1] = (dp[i + 1][j][k + 1] + dp[i][j][k]) % MOD;
						else dp[i + 1][j][1] = (dp[i + 1][j][1] + dp[i][j][k]) % MOD;
					}
					else {
						dp[i + 1][j][0] = (dp[i + 1][j][0] + dp[i][j][k]) % MOD;
					}
				}
			}
		}
	}
	ll ans = 0;
	for (int i = 0; i <= 252; i++)ans = (ans + dp[n][x][i]) % MOD;
	cout << ans << endl;
	return 0;
}

Submission Info

Judge Result