Submission #337896

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <cstring>
#include <functional>
#include <cmath>
#include <utility>
#include <complex>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
#define rep1(i,n) for(int i=1;i<=(n);++i)
#define all(c) (c).begin(),(c).end()
#define fs first
#define sc second
#define pb push_back
#define show(x) cout << #x << " " << x << endl
typedef long long ll;
ll mod=1e9+7;
void add(ll &x,ll y){
	x+=y;
	x%=mod;
}
ll dp[253][60][253];
int main(){
	int N,X;
	string s;
	cin>>N>>X>>s;
	dp[0][0][0]=1;
	rep(i,N){
		rep(j,60){
			rep(k,X+1){
				if(dp[i][j][k]==0) continue;
				if(k==X){
					add(dp[i+1][j][k],dp[i][j][k]*(s[i]=='?'?10:1));
					continue;
				}
				if(j%2==0){
					if((s[i]=='2'||s[i]=='?')){
						add(dp[i+1][j+1][k],dp[i][j][k]);
						if(s[i]=='?'){
							add(dp[i+1][0][k],dp[i][j][k]*9);
						}
					}else{
						add(dp[i+1][0][k],dp[i][j][k]);
					}
				}else{
					if((s[i]=='5'||s[i]=='?')){
						add(dp[i+1][j+1][min(X,k+(j+1)/2)],dp[i][j][k]);
						if(s[i]=='?'){
							add(dp[i+1][0][k],dp[i][j][k]*8);
							add(dp[i+1][1][k],dp[i][j][k]);
						}
					}else{
						if(s[i]=='2') add(dp[i+1][1][k],dp[i][j][k]);
						else add(dp[i+1][0][k],dp[i][j][k]);
					}
				}
			}
		}
	}
	ll ans=0;
	rep(j,60) add(ans,dp[N][j][X]);
	cout<<ans<<endl;
}

Submission Info

Judge Result