Submission #621202

---

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++){
	  
	  //直前の文字が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] += 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'){
	      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] += 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

Judge Result