Submission #337939


Source Code Expand

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<vector>
#include<set>
#include<list>
#include<queue>
#include<cmath>
#include<functional>
#include<algorithm>
#define INF (1<<29)
#define rep(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;

#define MOD 1000000007

long long dp[253][253][253][2];


int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,x;
	cin>>n>>x;
	string s;
	cin>>s;

	dp[0][0][0][0]=1; 
	rep(i,s.size()){
		rep(j,x+1){//freq
			rep(k,s.size()){//25seq
				rep(two,2){
					if(!dp[i][j][k][two])continue;
					long long v=dp[i][j][k][two];
					if(s[i]=='?'){
						if(two==0)(dp[i+1][j][k][1]+=v)%=MOD;
						else (dp[i+1][j][0][1]+=v)%=MOD;
						
						if(two==0)(dp[i+1][j][0][0]+=v)%=MOD;
						else {
							(dp[i+1][min(j+k+1,x)][k+1][0]+=v)%=MOD;
						}

						(dp[i+1][j][0][0]+=v*8)%=MOD;

					}else{
						int n=s[i]-'0';
						if(n==2){
							if(two==0)(dp[i+1][j][k][1]+=v)%=MOD;
							else (dp[i+1][j][0][1]+=v)%=MOD;
						}else if(n==5){
							if(two==0)(dp[i+1][j][0][0]+=v)%=MOD;
							else {
								(dp[i+1][min(j+k+1,x)][k+1][0]+=v)%=MOD;
							}
						}else{
							(dp[i+1][j][0][0]+=v)%=MOD;
						}
					}
				}
			}
		}
	}
	int ans=0;
	rep(i,s.size()){
		rep(j,2){
			(ans+=dp[s.size()][x][i][j])%=MOD;
		}
	}
	cout<<ans<<endl;

	return 0;
}

Submission Info

Submission Time
Task A - ニコニコ文字列2
User hirokazu1020
Language C++ (G++ 4.6.4)
Score 20
Code Size 1408 Byte
Status AC
Exec Time 666 ms
Memory 217128 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 20 / 20
Status
AC × 2
AC × 22
Set Name Test Cases
Sample sample_01.txt, sample_02.txt
All subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt
Case Name Status Exec Time Memory
sample_01.txt AC 22 ms 928 KB
sample_02.txt AC 22 ms 1040 KB
subtask1_01.txt AC 22 ms 876 KB
subtask1_02.txt AC 23 ms 728 KB
subtask1_03.txt AC 23 ms 728 KB
subtask1_04.txt AC 23 ms 728 KB
subtask1_05.txt AC 31 ms 3356 KB
subtask1_06.txt AC 84 ms 18604 KB
subtask1_07.txt AC 39 ms 3244 KB
subtask1_08.txt AC 116 ms 27684 KB
subtask1_09.txt AC 58 ms 12836 KB
subtask1_10.txt AC 40 ms 5420 KB
subtask1_11.txt AC 50 ms 9252 KB
subtask1_12.txt AC 276 ms 22428 KB
subtask1_13.txt AC 41 ms 4320 KB
subtask1_14.txt AC 362 ms 66736 KB
subtask1_15.txt AC 500 ms 141596 KB
subtask1_16.txt AC 482 ms 131236 KB
subtask1_17.txt AC 659 ms 217116 KB
subtask1_18.txt AC 240 ms 1700 KB
subtask1_19.txt AC 666 ms 217128 KB
subtask1_20.txt AC 482 ms 128800 KB
subtask1_21.txt AC 29 ms 2080 KB
subtask1_22.txt AC 28 ms 2088 KB