Submission #525076

---

Source Code Expand

/*
 * a.cc: A: 
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>

using namespace std;

/* constant */

const int MAX_N = 252;
const int MAX_X = 252;
const int MAX_L = 22; // MAX_L*(MAX_L+1)/2>=MAX_X

typedef long long ll;

const ll MOD = 1000000007;

/* typedef */

/* global variables */

ll dp[MAX_N + 1][MAX_X][MAX_L + 1][10];

/* subroutines */

inline void addmod(ll& a, ll& b) { a = (a + b) % MOD; }

/* main */

int main() {
  int n, x;
  string s;
  cin >> n >> x >> s;

  ll all = 1;
  for (int i = 0; i < n; i++)
    if (s[i] == '?') all = (all * 10) % MOD;
  //cout << all << endl;

  int maxl = 0;
  while (maxl * (maxl + 1) / 2 < x) maxl++;
  
  dp[0][0][0][0] = 1;
  
  for (int i = 0; i < n; i++) {
    int nd0, nd1;
    if (s[i] == '?') nd0 = 0, nd1 = 9;
    else nd0 = nd1 = s[i] - '0';

    for (int j = 0; j < x; j++)
      for (int l = 0; l < maxl; l++)
	for (int cd = 0; cd < 10; cd++)
	  if (dp[i][j][l][cd] > 0)
	    for (int nd = nd0; nd <= nd1; nd++) {
	      if (cd == 5 && nd == 2)
		addmod(dp[i + 1][j][l][nd], dp[i][j][l][cd]);
	      else if (cd == 2 && nd == 5) {
		int nj = j + (l + 1);
		if (nj < x)
		  addmod(dp[i + 1][nj][l + 1][nd], dp[i][j][l][cd]);
	      }
	      else
		addmod(dp[i + 1][j][0][nd], dp[i][j][l][cd]);
	    }
  }

  ll sum = 0;
  for (int j = 0; j < x; j++)
    for (int l = 0; l < maxl; l++)
      for (int d = 0; d < 10; d++)
	addmod(sum, dp[n][j][l][d]);

  printf("%lld\n", (all + MOD - sum) % MOD);

  /*
  for (int i = 0; i <= n; i++)
    for (int j = 0; j < x; j++)
      for (int l = 0; l < maxl; l++)
	for (int d = 0; d < 10; d++)
	  printf("dp[%d][%d][%d][%d]=%lld\n", i, j, l, d, dp[i][j][l][d]);
  */
  return 0;
}

Submission Info

Judge Result