Submission #3108253

---

Source Code Expand

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <utility>
#include <queue>
#include <set>
#include <map>
#include <deque>
#include <iomanip>
#include <cstdio>

using namespace std;
typedef  long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
#define  MP make_pair
#define  PB push_back
#define inf  1000000007
#define mod  1000000007
#define rep(i,n) for(int i=0;i<(int)(n);++i)


int main(){
    int n,x,p;
    cin >> n >> x >> p;
    vector<char>a(n);
    rep(i,n)cin >> a[i];
    vector<ll> c3(11);
    c3[0] = 1;
    for(int i=1;i<11;i++){
        c3[i]=3*c3[i-1];
    }
    vector<int> cs(177147);
    vector<int> ct(177147);
    for(int i=0;i<177147;i++){
        int s=0;
        int t=0;
        int tmp = i;
        for(int j=0;j<11;j++){
            if(tmp%3==1){
                s += 1<<j;
            }else if(tmp%3==2){
                t += 1<<j;
            }
            tmp/=3;
        }
        cs[i] = s;
        ct[i] = t;
    }
    vector<int> vs(2048);
    vector<int> vt(2048);
    for(int i=0;i<2048;i++){
        int tmp=0;
        int tmp2= 0;
        int s = i;
        for(int j=0;j<11;j++){
            if(s%2==1){
                tmp += c3[j];
                tmp2 += 2*c3[j];
            }            
            s/=2;
        }
        vs[i] = tmp;
        vt[i] = tmp2;
    }
    vector <ll>  dp(177147);
    dp[1] = 1;
    rep(zz,n){
        vector <ll>  dp2(177147);
        if(a[zz]!='?'){
            int k = a[zz]-'0';
            for(int i=0;i<177147;i++){
                int s=cs[i];
                int t=ct[i];
                int ss = s^(s<<k);
                ss &= 2047;
                int pp = s&(s<<k);
                pp &= 2047;
                s = ss;
                t |= (t<<k);
                t |= pp;
                t &= 2047;
                s -= s&t;
                int w = vs[s] + vt[t];
                dp2[w] = (dp2[w]+dp[i])%mod;
            }
        }else{
            for(int k=0;k<=p;k++){
                for(int i=0;i<177147;i++){
                    int s=cs[i];
                    int t=ct[i];
                    int ss = s^(s<<k);
                    ss &= 2047;
                    int pp = s&(s<<k);
                    pp &= 2047;
                    s = ss;
                    t |= (t<<k);
                    t |= pp;
                    t &= 2047;
                    s -= s&t;
                    int w = vs[s] + vt[t];
                    dp2[w] = (dp2[w]+dp[i])%mod;
                }
            }
        }
        dp = dp2;
        // for(int i=0;i<30;i++){
        //     cout << i << " " << dp[i] << endl;
        // }
    }
    ll ans = 0;
    for(int i=0;i<177147;i++){
        if(cs[i]&(1<<x)){
            ans = (ans+dp[i])%mod;
        }
    }
    cout << ans << endl;
    return 0;
}

Submission Info

Judge Result