Submission #440493

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <cassert>
#include <cstring>
#include <vector>
#include <valarray>
#include <array>
#include <queue>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <complex>
#include <random>
 
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

const ll MD = 1e9+7;

ll dp[300][300][300];
int n, x;
string s;

ll solve(int a, int b, int k) {
    k = max(0, k);
    if (b == n) {
        if (k) return 0;
        return 1;
    }
    if (dp[a][b][k] != -1) return dp[a][b][k];
    ll &res = dp[a][b][k];
    if (a%2 == 0) {
        if (s[b] == '2') {
            res = solve(a+1, b+1, k);
        } else if (s[b] != '?') {
            res = solve(0, b+1, k);
        } else {
            res = solve(a+1, b+1, k) + 9*solve(0, b+1, k);
        }
    } else {
        if (s[b] == '2') {
            res = solve(1, b+1, k);
        } else if (s[b] == '5') {
            res = solve(a+1, b+1, k-(a+1)/2);
        } else if (s[b] != '?') {
            res = solve(0, b+1, k);
        } else {
            res = solve(1, b+1, k)+solve(a+1, b+1, k-(a+1)/2)+8*solve(0, b+1, k);
        }
    }
    res %= MD;
    return res;
}

int main() {
    memset(dp, -1, sizeof(dp));
    cin >> n >> x;
    cin >> s;

    cout << solve(0, 0, x) << endl;
    return 0;
}

Submission Info

Judge Result