Submission #337867

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <map>
#include <cmath>
using namespace std;

int N,X;
string s;

int dp[300][300][300][2];
int dfs(int x,int n,int m,int a){
	n = min(255,n);
	m = min(255,m);
	
	if( dp[x][n][m][a] != -1) return dp[x][n][m][a];
	if( x == s.size() ) return n >= X;
	vector<int> p;
	if( s[x] == '?' ) for(int i = 0 ; i < 10 ; i++) p.push_back(i);
	else p.push_back(s[x]-'0');
	int ans = 0;
	for(int i = 0 ; i < p.size() ; i++){
		int t = p[i];
		if( a == 0 && t == 2 ){
			ans += dfs(x+1,n,m,1);
		}else if( a == 1 && t == 5 ){
			ans += dfs(x+1,n+m+1,m+1,0);
		}else if( t == 2 ){
			ans += dfs(x+1,n,0,1);
		}else{
			ans += dfs(x+1,n,0,0);
		}
		ans %= 1000000007;
		
	}
	return dp[x][n][m][a] = ans % 1000000007;
}
int main(){	
	memset(dp,-1,sizeof(dp));
	cin >> N >> X;
	cin >> s;
	cout << dfs(0,0,0,0) << endl;
}

Submission Info

Judge Result