Submission #621204


Source Code Expand

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
#include <queue>
#include <complex>
 
#define INF 100000000
#define YJ 1145141919
#define INF_INT_MAX 2147483647
#define INF_LL_MAX 9223372036854775807
#define EPS 1e-10
#define Pi acos(-1)
#define LL long long
#define ULL unsigned long long
#define LD long double 
 
using namespace std;
 
#define MAX_N 255
#define MAX_X 255

#define mod 1000000007

int N, X;
string S;

//dp[pos][nico_counting_cnt][nico_count][2]
LL dp[MAX_N][MAX_N][MAX_X][2];

int main(){

  cin >> N >> X;
  cin >> S;

  X--;

  dp[0][0][0][0] = 1;

  for(int pos = 0; pos < N; pos++){
    for(int nico_counting_cnt = 0; nico_counting_cnt <= X; nico_counting_cnt++){
      for(int nico_cnt = 0; nico_cnt <= X; nico_cnt++){
	for(int flag2 = 0; flag2 < 2; flag2++){
	  
	  if(dp[pos][nico_counting_cnt][nico_cnt][flag2] == 0)
	    continue;

	  //直前の文字が2であったとき
	  if(flag2){
	    
	    if(S[pos] == '?'){
	      
	      //?に5を割り当てるとニコニコ文字列になる
	      if(nico_counting_cnt + 1 + nico_cnt <= X){
		dp[pos+1][nico_counting_cnt + 1][nico_counting_cnt + 1 + nico_cnt][0] += dp[pos][nico_counting_cnt][nico_cnt][1];
		dp[pos+1][nico_counting_cnt + 1][nico_counting_cnt + 1 + nico_cnt][0] %= mod;
	      }
	      //?に5以外の数字を割り当てる
	      
	      //2を割り当てない場合
	      dp[pos+1][0][nico_cnt][0] += (LL)8*dp[pos][nico_counting_cnt][nico_cnt][1];
	      dp[pos+1][0][nico_cnt][0] %= mod;
	      
	      //2を割り当てる場合
	      dp[pos+1][0][nico_cnt][1] += dp[pos][nico_counting_cnt][nico_cnt][1];
	      dp[pos+1][0][nico_cnt][1] %= mod;

	    }
	    else if(S[pos] == '2'){
	      
	      dp[pos+1][0][nico_cnt][1] += dp[pos][nico_counting_cnt][nico_cnt][1];
	      dp[pos+1][0][nico_cnt][1] %= mod;

	    }
	    else if(S[pos] == '5'){
	      if(nico_counting_cnt + 1 + nico_cnt <= X){
		dp[pos+1][nico_counting_cnt + 1][nico_counting_cnt + 1 + nico_cnt][0] += dp[pos][nico_counting_cnt][nico_cnt][1];
		dp[pos+1][nico_counting_cnt + 1][nico_counting_cnt + 1 + nico_cnt][0] %= mod;
	      }
	    }
	    else{
	      dp[pos+1][0][nico_cnt][0] += dp[pos][nico_counting_cnt][nico_cnt][1];
	      dp[pos+1][0][nico_cnt][0] %= mod;
	    }

	  }
	  
	  //直前の文字が2以外であった時
	  else{
	    
	    if(S[pos] == '?'){
	      
	      //?に2を割り当てればnico_countingを継続した状態を引き継げる
	      dp[pos+1][nico_counting_cnt][nico_cnt][1] += 
		dp[pos][nico_counting_cnt][nico_cnt][0];
	      dp[pos+1][nico_counting_cnt][nico_cnt][1] %= mod;
	      
	      //?に2以外を割り当てる場合
	      dp[pos+1][0][nico_cnt][0] += (LL)9*dp[pos][nico_counting_cnt][nico_cnt][0];
	      dp[pos+1][0][nico_cnt][0] %= mod;

	    }
	    else if(S[pos] == '2'){
	      
	      dp[pos+1][nico_counting_cnt][nico_cnt][1] += 
		dp[pos][nico_counting_cnt][nico_cnt][0];
	      dp[pos+1][nico_counting_cnt][nico_cnt][1] %= mod;

	    }
	    else{
	      
	      dp[pos+1][0][nico_cnt][0] += dp[pos][nico_counting_cnt][nico_cnt][0];
	      dp[pos+1][0][nico_cnt][0] %= mod;

	    }

	  }

	}
      }
    }
  }
  
  LL ans = 1;
  for(int i = 0; i < N; i++){
    if(S[i] == '?'){
      ans *= 10;
      ans %= mod;
    }
  }
  
  LL tmp = 0;
  for(int nico_counting_cnt = 0; nico_counting_cnt <= X; nico_counting_cnt++){
    for(int nico_cnt = 0; nico_cnt <= X; nico_cnt++){
      for(int flag2 = 0; flag2 < 2; flag2++){
	if(dp[N][nico_counting_cnt][nico_cnt][flag2] > 0){
	  tmp += dp[N][nico_counting_cnt][nico_cnt][flag2];
	  tmp %= mod;
	}
      }
    }
  }
  
  ans -= tmp;
  if(ans < 0)
    ans += mod;
  cout << ans%mod << endl;
  
  /*
  for(int i = 0; i <= N; i++){
    for(int nico_counting_cnt = 0; nico_counting_cnt <= X; nico_counting_cnt++){
      for(int nico_cnt = 0; nico_cnt <= X; nico_cnt++){
	for(int flag2 = 0; flag2 < 2; flag2++){
	  fprintf(stderr, "(i,nico_counting_cnt, nico_cnt, flag2),(%d,%d,%d,%d) := %lld\n", i, nico_counting_cnt, nico_cnt, flag2, dp[i][nico_counting_cnt][nico_cnt][flag2]);
	}
      }
    }
  }
  */

  return 0;

}

Submission Info

Submission Time
Task A - ニコニコ文字列2
User takoshi
Language C++ (G++ 4.6.4)
Score 20
Code Size 4658 Byte
Status AC
Exec Time 340 ms
Memory 22064 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 20 / 20
Status
AC × 2
AC × 22
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 26 ms 1044 KB
sample_02.txt AC 27 ms 1076 KB
subtask1_01.txt AC 25 ms 956 KB
subtask1_02.txt AC 24 ms 1052 KB
subtask1_03.txt AC 29 ms 1052 KB
subtask1_04.txt AC 26 ms 1048 KB
subtask1_05.txt AC 33 ms 1724 KB
subtask1_06.txt AC 67 ms 1908 KB
subtask1_07.txt AC 41 ms 1452 KB
subtask1_08.txt AC 91 ms 4784 KB
subtask1_09.txt AC 47 ms 2864 KB
subtask1_10.txt AC 44 ms 2096 KB
subtask1_11.txt AC 40 ms 2096 KB
subtask1_12.txt AC 276 ms 2352 KB
subtask1_13.txt AC 36 ms 1844 KB
subtask1_14.txt AC 279 ms 3116 KB
subtask1_15.txt AC 298 ms 10668 KB
subtask1_16.txt AC 298 ms 9900 KB
subtask1_17.txt AC 340 ms 22064 KB
subtask1_18.txt AC 278 ms 1844 KB
subtask1_19.txt AC 338 ms 20540 KB
subtask1_20.txt AC 301 ms 10292 KB
subtask1_21.txt AC 27 ms 1044 KB
subtask1_22.txt AC 26 ms 944 KB