Submission #337915
Source Code Expand
import java.io.*;
import java.math.*;
import java.util.*;
import static java.util.Arrays.*;
public class Main {
private static final int mod = (int)1e9+7;
final Random random = new Random(0);
final IOFast io = new IOFast();
/// MAIN CODE
public void run() throws IOException {
// int TEST_CASE = Integer.parseInt(new String(io.nextLine()).trim());
int TEST_CASE = 1;
while(TEST_CASE-- != 0) {
n = io.nextInt();
int X = io.nextInt();
digit = new int[n];
char[] cs = io.next();
for(int i = 0; i < n; i++) {
digit[i] = cs[i] == '?' ? -1 : cs[i] - '0';
}
// int cnt = 0;
// for(int i = 0; i < 10000; i++) {
// String s = Integer.toString(i);
// while(s.length() < 4) s = "0" + s;
// if(s.indexOf("25") >= 0 && s.charAt(2) == '5') cnt++;
// }
// System.err.println(cnt);
memo = new long[n][2][X+1][n];
for(long[][][] c : memo) for(long[][] a : c) for(long[] b : a) Arrays.fill(b, -1L);
io.out.println(rec(0, X, 0));
}
}
int n;
int[] digit;
long[][][][] memo;
long rec(int idx, int m, int l) {
if(idx >= n) {
l /= 2;
return m - l * (l+1) / 2 <= 0 ? 1 : 0;
}
m = Math.max(m, 0);
if(memo[idx][0][m][l] != -1) return memo[idx][0][m][l];
long res = 0;
for(int i = 0; i < 10; i++) {
if(digit[idx] != -1 && digit[idx] != i) continue;
int nm = m;
int nl = 0;
if(i == 2 && l%2 == 0 || i == 5 && l%2 == 1) {
nl = l + 1;
}
else {
nl = i == 2 ? 1 : 0;
int x = l / 2;
nm -= x * (x + 1) / 2;
}
res += rec(idx + 1, nm, nl);
if(res >= mod) res -= mod;
}
return memo[idx][0][m][l] = res;
}
/// TEMPLATE
static int gcd(int n, int r) { return r == 0 ? n : gcd(r, n%r); }
static long gcd(long n, long r) { return r == 0 ? n : gcd(r, n%r); }
static <T> void swap(T[] x, int i, int j) { T t = x[i]; x[i] = x[j]; x[j] = t; }
static void swap(int[] x, int i, int j) { int t = x[i]; x[i] = x[j]; x[j] = t; }
void main() throws IOException {
// IOFast.setFileIO("rle-size.in", "rle-size.out");
try { run(); }
catch (EndOfFileRuntimeException e) { }
io.out.flush();
}
public static void main(String[] args) throws IOException { new Main().main(); }
static class EndOfFileRuntimeException extends RuntimeException {
private static final long serialVersionUID = -8565341110209207657L; }
static
public class IOFast {
private BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
private PrintWriter out = new PrintWriter(System.out);
void setFileIn(String ins) throws IOException { in.close(); in = new BufferedReader(new FileReader(ins)); }
void setFileOut(String outs) throws IOException { out.flush(); out.close(); out = new PrintWriter(new FileWriter(outs)); }
void setFileIO(String ins, String outs) throws IOException { setFileIn(ins); setFileOut(outs); }
private static int pos, readLen;
private static final char[] buffer = new char[1024 * 8];
private static char[] str = new char[500*8*2];
private static boolean[] isDigit = new boolean[256];
private static boolean[] isSpace = new boolean[256];
private static boolean[] isLineSep = new boolean[256];
static { for(int i = 0; i < 10; i++) { isDigit['0' + i] = true; } isDigit['-'] = true; isSpace[' '] = isSpace['\r'] = isSpace['\n'] = isSpace['\t'] = true; isLineSep['\r'] = isLineSep['\n'] = true; }
public int read() throws IOException { if(pos >= readLen) { pos = 0; readLen = in.read(buffer); if(readLen <= 0) { throw new EndOfFileRuntimeException(); } } return buffer[pos++]; }
public int nextInt() throws IOException { int len = 0; str[len++] = nextChar(); len = reads(len, isSpace); int i = 0; int ret = 0; if(str[0] == '-') { i = 1; } for(; i < len; i++) ret = ret * 10 + str[i] - '0'; if(str[0] == '-') { ret = -ret; } return ret; }
public long nextLong() throws IOException { int len = 0; str[len++] = nextChar(); len = reads(len, isSpace); int i = 0; long ret = 0; if(str[0] == '-') { i = 1; } for(; i < len; i++) ret = ret * 10 + str[i] - '0'; if(str[0] == '-') { ret = -ret; } return ret; }
public char nextChar() throws IOException { while(true) { final int c = read(); if(!isSpace[c]) { return (char)c; } } }
int reads(int len, boolean[] accept) throws IOException { try { while(true) { final int c = read(); if(accept[c]) { break; } if(str.length == len) { char[] rep = new char[str.length * 3 / 2]; System.arraycopy(str, 0, rep, 0, str.length); str = rep; } str[len++] = (char)c; } } catch(EndOfFileRuntimeException e) { ; } return len; }
int reads(char[] cs, int len, boolean[] accept) throws IOException { try { while(true) { final int c = read(); if(accept[c]) { break; } cs[len++] = (char)c; } } catch(EndOfFileRuntimeException e) { ; } return len; }
public char[] nextLine() throws IOException { int len = 0; str[len++] = nextChar(); len = reads(len, isLineSep); try { if(str[len-1] == '\r') { len--; read(); } } catch(EndOfFileRuntimeException e) { ; } return Arrays.copyOf(str, len); }
public String nextString() throws IOException { return new String(next()); }
public char[] next() throws IOException { int len = 0; str[len++] = nextChar(); len = reads(len, isSpace); return Arrays.copyOf(str, len); }
public int next(char[] cs) throws IOException { int len = 0; cs[len++] = nextChar(); len = reads(cs, len, isSpace); return len; }
public double nextDouble() throws IOException { return Double.parseDouble(nextString()); }
public long[] nextLongArray(final int n) throws IOException { final long[] res = new long[n]; for(int i = 0; i < n; i++) { res[i] = nextLong(); } return res; }
public int[] nextIntArray(final int n) throws IOException { final int[] res = new int[n]; for(int i = 0; i < n; i++) { res[i] = nextInt(); } return res; }
public int[][] nextIntArray2D(final int n, final int k) throws IOException { final int[][] res = new int[n][]; for(int i = 0; i < n; i++) { res[i] = nextIntArray(k); } return res; }
public int[][] nextIntArray2DWithIndex(final int n, final int k) throws IOException { final int[][] res = new int[n][k+1]; for(int i = 0; i < n; i++) { for(int j = 0; j < k; j++) { res[i][j] = nextInt(); } res[i][k] = i; } return res; }
public double[] nextDoubleArray(final int n) throws IOException { final double[] res = new double[n]; for(int i = 0; i < n; i++) { res[i] = nextDouble(); } return res; }
}
}
Submission Info
Submission Time |
|
Task |
A - ニコニコ文字列2 |
User |
tanzaku |
Language |
Java (OpenJDK 1.7.0) |
Score |
0 |
Code Size |
6460 Byte |
Status |
MLE |
Exec Time |
1432 ms |
Memory |
269752 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 20 |
Status |
|
|
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 |
416 ms |
20968 KB |
sample_02.txt |
AC |
402 ms |
20768 KB |
subtask1_01.txt |
AC |
405 ms |
20760 KB |
subtask1_02.txt |
AC |
405 ms |
20752 KB |
subtask1_03.txt |
AC |
413 ms |
20736 KB |
subtask1_04.txt |
AC |
415 ms |
20676 KB |
subtask1_05.txt |
AC |
462 ms |
25024 KB |
subtask1_06.txt |
AC |
534 ms |
52848 KB |
subtask1_07.txt |
AC |
471 ms |
36208 KB |
subtask1_08.txt |
AC |
531 ms |
45732 KB |
subtask1_09.txt |
AC |
446 ms |
27308 KB |
subtask1_10.txt |
AC |
437 ms |
23852 KB |
subtask1_11.txt |
AC |
467 ms |
36220 KB |
subtask1_12.txt |
MLE |
1414 ms |
269616 KB |
subtask1_13.txt |
AC |
467 ms |
36136 KB |
subtask1_14.txt |
MLE |
1424 ms |
269752 KB |
subtask1_15.txt |
MLE |
1420 ms |
269748 KB |
subtask1_16.txt |
MLE |
1432 ms |
269640 KB |
subtask1_17.txt |
MLE |
1410 ms |
269748 KB |
subtask1_18.txt |
MLE |
1421 ms |
269620 KB |
subtask1_19.txt |
MLE |
1426 ms |
269620 KB |
subtask1_20.txt |
MLE |
1416 ms |
269624 KB |
subtask1_21.txt |
AC |
443 ms |
23652 KB |
subtask1_22.txt |
AC |
444 ms |
23680 KB |