Submission #4066144

---

Source Code Expand

// #define _GLIBCXX_DEBUG // for STL debug (optional)
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define int long long int
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
typedef pair<int, int> pii;
typedef long long ll;
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const ll INF = 1001001001001001LL;
const ll MOD = 1000000007LL;

const int LEN = 300;
const int SQRT = 24;

int calc(int x) {
    return x * (x + 1) / 2;
}

// (252, 252, 24, 100)
int dp[2][LEN][SQRT+1][100];
signed main() {
    int N, X; cin >> N >> X;

    string s; cin >> s;
    s += "0"; N++;

    dp[0][0][0][0] = 1;
    for(int i=0; i<N; i++) {
        int cur = i % 2, nxt = 1 - cur;
        for(int j=0; j<=X; j++) {
            for(int k=0; k<=SQRT; k++) {
                for(int d=0; d<100; d++) {
                    if(dp[cur][j][k][d] == 0) continue;
                    for(int x=0; x<10; x++) {
                        if(s[i] != '?' and s[i] - '0' != x) continue;
                        int nd = (d * 10 + x) % 100, nj = j, nk = k;
                        if(nd == 25) nk = min(nk + 1, SQRT);
                        else if(nd != 52) nj = min(X, j + calc(k)), nk = 0;

                        (dp[nxt][nj][nk][nd] += dp[cur][j][k][d]) %= MOD;
                    }
                    dp[cur][j][k][d] = 0;
                }
            }
        }
    }

    int ans = 0;
    for(int i=0; i<100; i++) (ans += dp[N%2][X][0][i]) %= MOD;
    cout << ans << endl;
    return 0;
}

Submission Info

Judge Result