Submission #3923405

---

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <bitset>
#include <set>
#include <cmath>
using namespace std;
#define MOD 1000000007

long long dp[303][303][303];

void add(long long &a, long long x){
    a = (a + x) % MOD;
}

int main(){
    int N, K;
    string S;
    cin >> N >> K >> S;
    dp[0][0][0] = 1;
    for(int i=0; i<N; i++){
        for(int j=0; j<=K; j++){
            for(int k=0; k<=K; k++){
                if(S[i]=='1') add(dp[i+1][j+1][max(0, k-1)], dp[i][j][k]);
                if(S[i]=='0') add(dp[i+1][max(0, j-1)][k+1], dp[i][j][k]);
                if(S[i]=='?'){
                    add(dp[i+1][j+1][max(0, k-1)], dp[i][j][k]);
                    add(dp[i+1][max(0, j-1)][k+1], dp[i][j][k]);
                }
            }
        }
    }

    long long ans = 0;
    for(int j=0; j<=K; j++)
        for(int k=0; k<=K; k++)
            add(ans, dp[N][j][k]);
    cout << ans << endl;
    return 0;
}

Submission Info

Judge Result