Submission #4063870

---

Source Code Expand

#include <iostream>
#include <vector>
using namespace std;
const long long mod = (1e9)+7;

long long dp[2][253][130][10];

int main(){
  int N, X;
  string S;
  cin >> N >> X >> S;
  dp[0][0][0][0] += 1;
  for(int i = 0; i < N; ++i){
    for(int j = 0; j <= X; ++j){
      for(int k = 0; k < 130; ++k){
        for(int l = 0; l < 10; ++l){
          long long t = dp[i%2][j][k][l];
          dp[i%2][j][k][l] = 0;
          if(t == 0) continue;
          if(S[i] == '?'){
            for(int m = 0; m < 10; ++m){
              if(l == 5 and m == 2){
                dp[(i+1)%2][j][k][m] += t;
                dp[(i+1)%2][j][k][m] %= mod;
                continue;
              }
              if(l == 2 and m == 5){
                dp[(i+1)%2][min(j+k+1,X)][k+1][m] += t;
                dp[(i+1)%2][min(j+k+1,X)][k+1][m] %= mod;
                continue;
              }
              dp[(i+1)%2][j][0][m] += t;
              dp[(i+1)%2][j][0][m] %= mod;
            }
            continue;
          }
          if(l == 2 and S[i] == '5'){
            dp[(i+1)%2][min(j+k+1,X)][k+1][5] += t;
            dp[(i+1)%2][min(j+k+1,X)][k+1][5] %= mod;
            continue;
          }
          if(l == 5 and S[i] == '2'){
            dp[(i+1)%2][j][k][2] += t;
            dp[(i+1)%2][j][k][2] %= mod;
            continue;
          }
          dp[(i+1)%2][j][0][S[i]-'0'] += t;
          dp[(i+1)%2][j][0][S[i]-'0'] %= mod;
        }
      }
    }
  }
  long long ans = 0;
  for(int i = 0; i < 130; ++i){
    for(int k = 0; k < 10; ++k){
      ans += dp[N%2][X][i][k];
      ans %= mod;
    }
  }
  cout << ans << endl;
}

Submission Info

Judge Result