Submission #525072


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 sd = (s[i] == '?') ? -1 : 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 = 0; nd < 10; nd++)
	      if (sd == -1 || sd == 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 - sum);

  /*
  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

Submission Time
Task A - ニコニコ文字列2
User tnakao
Language C++ (G++ 4.6.4)
Score 0
Code Size 2010 Byte
Status WA
Exec Time 477 ms
Memory 100020 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 20
Status
AC × 2
AC × 16
WA × 6
Set Name Test Cases
Sample sample_01.txt, sample_02.txt
All subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt
Case Name Status Exec Time Memory
sample_01.txt AC 27 ms 1120 KB
sample_02.txt AC 27 ms 1076 KB
subtask1_01.txt AC 26 ms 1044 KB
subtask1_02.txt AC 27 ms 1048 KB
subtask1_03.txt AC 26 ms 1044 KB
subtask1_04.txt AC 26 ms 1048 KB
subtask1_05.txt WA 32 ms 2228 KB
subtask1_06.txt AC 69 ms 9380 KB
subtask1_07.txt AC 39 ms 2140 KB
subtask1_08.txt AC 102 ms 14304 KB
subtask1_09.txt WA 52 ms 6576 KB
subtask1_10.txt WA 38 ms 3376 KB
subtask1_11.txt WA 43 ms 5172 KB
subtask1_12.txt AC 184 ms 11440 KB
subtask1_13.txt AC 45 ms 2392 KB
subtask1_14.txt AC 225 ms 31544 KB
subtask1_15.txt WA 305 ms 66488 KB
subtask1_16.txt AC 295 ms 62388 KB
subtask1_17.txt AC 477 ms 100020 KB
subtask1_18.txt AC 153 ms 2020 KB
subtask1_19.txt WA 454 ms 100020 KB
subtask1_20.txt AC 294 ms 61624 KB
subtask1_21.txt AC 27 ms 1052 KB
subtask1_22.txt AC 26 ms 1048 KB