Submission #337875

---

Source Code Expand

#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

#define pb push_back
#define mod 1000000007
typedef long long ll;

int n,x,c;
ll dp[255][255][255][2];
string s;

int main()
{
	cin >> n >> x;
	cin >> s;
	dp[0][0][0][0] = 1ll;
	for(int i=0;i<s.size();i++)
	{
		for(int j=0;j<=252;j++)
		{
			for(int k=0;k<=252;k++)
			{
				if(dp[i][j][k][0] == 0) goto nxt;
				
				c = (s[i]=='?')?10:1;
				if(s[i]=='?' || s[i]=='2')
				{
					dp[i+1][j][k][1] = (dp[i+1][j][k][1]+dp[i][j][k][0])%mod;
					c--;
				}
				dp[i+1][j][0][0] = (dp[i+1][j][0][0]+dp[i][j][k][0]*1ll*c)%mod;
				
				nxt:;
				
				if(dp[i][j][k][1] == 0) continue;
				
				c = (s[i]=='?')?10:1;
				if(s[i]=='?' || s[i]=='5')
				{
					dp[i+1][min(252,j+k+1)][k+1][0] = (dp[i+1][min(252,j+k+1)][k+1][0]+dp[i][j][k][1])%mod;
					c--;
				}
				if(s[i]=='?' || s[i]=='2')
				{
					dp[i+1][j][0][1] = (dp[i+1][j][0][1]+dp[i][j][k][1])%mod;
					c--;
				}
				dp[i+1][j][0][0] = (dp[i+1][j][0][0]+dp[i][j][k][1]*1ll*c)%mod;
				
			}
		}
	}
	ll res = 0;
	for(int i=x;i<=252;i++) for(int j=0;j<=252;j++) res = (res+dp[s.size()][i][j][0]+dp[s.size()][i][j][1])%mod;
	cout << res << endl;
}

Submission Info

Judge Result