Submission #2226992

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

typedef long long lli;
typedef vector<lli> vll;
typedef vector<bool> vbl;
typedef vector<vector<lli>> mat;
typedef vector<unordered_map<lli,lli>> graph;

const lli mod = 1000000007;

lli n,k;
string d;
vector<mat> dp;
lli ans;

int main(){
  cin >> n >> k >> d;
  dp = vector<mat>(n+1,mat(k+1,vll(k+1)));
  dp[0][0][0] = 1;
  for(lli s = 0;s < n;s++){
    for(lli t = 0;t <= k;t++){
      for(lli u = 0;u <= k;u++){
        dp[s][t][u] %= mod;
        if(t+1 <= k && (d[s] == '1' || d[s] == '?')) dp[s+1][t+1][max(0ll,u-1)] += dp[s][t][u];//1
        if(u+1 <= k && (d[s] == '0' || d[s] == '?')) dp[s+1][max(0ll,t-1)][u+1] += dp[s][t][u];//0

      }
    }
  }
  for(lli i = 0;i <= k;i++){
    for(lli j = 0;j <= k;j++){
      ans += dp[n][i][j];
    }
  }
  cout << ans << endl;
  return 0;

}

Submission Info

Judge Result