Submission #3915885

---

Source Code Expand

#include <bits/stdc++.h>
#define FOR(v, a, b) for(int v = (a); v < (b); ++v)
#define FORE(v, a, b) for(int v = (a); v <= (b); ++v)
#define REP(v, n) FOR(v, 0, n)
#define REPE(v, n) FORE(v, 0, n)
#define REV(v, a, b) for(int v = (a); v >= (b); --v)
#define ALL(x) (x).begin(), (x).end()
#define LLI long long int
using namespace std;
template <typename T> using V = vector<T>;
template <typename T, typename U> using P = pair<T,U>;
template <typename I> void join(ostream &ost, I s, I t, string d=" "){for(auto i=s; i!=t; ++i){if(i!=s)ost<<d; ost<<*i;}ost<<endl;}

LLI dp[310][310][310];

const LLI mod = 1e9+7;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);

  int N,K; cin >> N >> K;
  string s; cin >> s;

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

  REP(i,N){
    REPE(j,N){
      REPE(k,N){
	if(abs(j-k) > K) continue;

	if(s[i] == '0' || s[i] == '?') (dp[i+1][j+1][max(0,k-1)] += dp[i][j][k]) %= mod;
	if(s[i] == '1' || s[i] == '?') (dp[i+1][max(0,j-1)][k+1] += dp[i][j][k]) %= mod;
      }
    }
  }

  LLI ans = 0;

  REPE(j,N) REPE(k,N) if(abs(j-k) <= K) (ans += dp[N][j][k]) %= mod;
  
  
  cout << ans << endl;
  
  return 0;
}

Submission Info

Judge Result