Submission #4030153

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
using P = pair<ll, ll>;
const ll INF = 5e15;
const ll MOD = 1e9 + 7;

vector<vector<ll>> empty(620, vector<ll>(620));
decltype(empty) dp;

int main(){
    ll N, K;
    string S;
    cin >> N >> K >> S;
    dp = empty;
    ll idx_dummy[630] = {};
    ll *idx = idx_dummy + 310;
    for(ll i = 0; i <= 620; i++) idx[i - 310] = i;
    dp[idx[0]][idx[0]] = 1;
    for(ll i = 0; i < N; i++){
        char c = S[i];
        auto tmp = empty;
        for(ll left = -K; left <= K; left++){
            for(ll right = left; right <= K; right++){
                // add 0
                if(c != '1'){
                    (tmp[idx[left]][idx[max<ll>(1, right)]] += dp[idx[left - 1]][idx[right - 1]]) %= MOD;
                }
                if(c != '0'){
                    (tmp[idx[min<ll>(-1, left)]][idx[right]] += dp[idx[left + 1]][idx[right + 1]]) %= MOD;
                }
            }
        }
        dp = tmp;
    }
    ll ans = 0;
    for(ll i = -K; i <= K; i++) for(ll j = i; j <= K; j++) (ans += dp[idx[i]][idx[j]]) %= MOD;
    cout << ans << endl;
    return 0;
}

Submission Info

Judge Result