Submission #337909


Source Code Expand

#include <algorithm>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

using namespace std;

#define sz size()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(c) (c).begin(), (c).end()
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define clr(a, b) memset((a), (b) ,sizeof(a))

#define MOD 1000000007

long long dp[255][255][2];

int main(){
    int n,x;
    string s;
    cin>>n>>x;
    cin>>s;
    clr(dp,0);
    dp[0][0][0] = 1;
    rep(i,0,s.sz){
        rep(j,0,250){
            if(s[i]=='?'){
                // 2
                dp[i+1][j][1] += dp[i][j][0];
                dp[i+1][j][1] %= MOD;
                dp[i+1][j][1] += dp[i][j][1];
                dp[i+1][j][1] %= MOD;
                // 5
                dp[i+1][j][0] += dp[i][j][0];
                dp[i+1][j][0] %= MOD;
                dp[i+1][j+1][0] += dp[i][j][1];
                dp[i+1][j+1][0] %= MOD;
                // others
                dp[i+1][j][0] += dp[i][j][0]*8;
                dp[i+1][j][0] %= MOD;
                dp[i+1][j][0] += dp[i][j][1]*8;
                dp[i+1][j][0] %= MOD;
            }
            else{
                if(s[i]=='2'){
                    dp[i+1][j][1] += dp[i][j][0];
                    dp[i+1][j][1] %= MOD;
                    dp[i+1][j][1] += dp[i][j][1];
                    dp[i+1][j][1] %= MOD;
                }
                else if(s[i]=='5'){
                    dp[i+1][j][0] += dp[i][j][0];
                    dp[i+1][j][0] %= MOD;
                    dp[i+1][j+1][0] += dp[i][j][1];
                    dp[i+1][j+1][0] %= MOD;
                }
                else{
                    dp[i+1][j][0] += dp[i][j][0];
                    dp[i+1][j][0] %= MOD;
                    dp[i+1][j][0] += dp[i][j][1];
                    dp[i+1][j][0] %= MOD;
                }
            }
        }
    }
    long long ans = 0;
    ans += dp[s.sz][x][0];
    ans %= MOD;
    ans += dp[s.sz][x][1];
    ans %= MOD;
    cout << ans <<endl;
	return 0;
}

Submission Info

Submission Time
Task A - ニコニコ文字列2
User cls0001011
Language C++ (G++ 4.6.4)
Score 0
Code Size 2395 Byte
Status WA
Exec Time 27 ms
Memory 1828 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 20
Status
AC × 1
WA × 1
AC × 8
WA × 14
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 1696 KB
sample_02.txt WA 24 ms 1696 KB
subtask1_01.txt AC 24 ms 1700 KB
subtask1_02.txt AC 25 ms 1756 KB
subtask1_03.txt AC 25 ms 1700 KB
subtask1_04.txt AC 27 ms 1748 KB
subtask1_05.txt WA 24 ms 1696 KB
subtask1_06.txt AC 27 ms 1828 KB
subtask1_07.txt WA 25 ms 1704 KB
subtask1_08.txt WA 25 ms 1700 KB
subtask1_09.txt WA 27 ms 1812 KB
subtask1_10.txt WA 25 ms 1824 KB
subtask1_11.txt WA 24 ms 1828 KB
subtask1_12.txt AC 25 ms 1828 KB
subtask1_13.txt WA 26 ms 1700 KB
subtask1_14.txt AC 24 ms 1824 KB
subtask1_15.txt WA 26 ms 1828 KB
subtask1_16.txt WA 24 ms 1824 KB
subtask1_17.txt WA 26 ms 1828 KB
subtask1_18.txt AC 23 ms 1760 KB
subtask1_19.txt WA 25 ms 1700 KB
subtask1_20.txt WA 25 ms 1700 KB
subtask1_21.txt WA 25 ms 1700 KB
subtask1_22.txt WA 25 ms 1692 KB