Submission #1308069
Source Code Expand
import std.stdio, std.array, std.string, std.conv, std.algorithm; import std.typecons, std.range, std.random, std.math, std.container; import std.numeric, std.bigint, core.bitop; immutable long MOD = 10^^9 + 7; long powmod(long a, long x, long m) { long ret = 1; while (x) { if (x % 2) ret = ret * a % m; a = a * a % m; x /= 2; } return ret; } void main() { auto N = readln.chomp.to!int; auto S = readln.chomp; auto M = S.length.to!int; auto mem = new long[][](N + 1, N + 1); foreach (i; 0..N+1) fill(mem[i], -1); // dp(i, j) : i回キーを叩いてj文字入力されている場合の数 long dp(int i, int j) { if (i == 0 && j == 0) return 1; if (i <= 0 || j < 0) return 0; if (j > i) return 0; if (mem[i][j] >= 0) return mem[i][j]; long ret = 0; if (j == 0) { ret += dp(i - 1, j); ret %= MOD; } ret += dp(i - 1, j + 1); // Back Space ret %= MOD; ret += dp(i - 1, j - 1) * 2; // 0 or 1 ret %= MOD; return mem[i][j] = ret; } auto ans = dp(N, M); ans = ans * powmod(powmod(2, MOD-2, MOD), M, MOD) % MOD; ans.writeln; }
Submission Info
Submission Time | |
---|---|
Task | F - Unhappy Hacking |
User | nebukuro09 |
Language | D (LDC 0.17.0) |
Score | 800 |
Code Size | 1286 Byte |
Status | AC |
Exec Time | 315 ms |
Memory | 202876 KB |
Judge Result
Set Name | Sample | Sub1 | Sub2 | ||||||
---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 400 / 400 | 400 / 400 | ||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Sample | 0_01, 0_02, 0_03 |
Sub1 | 0_01, 0_02, 1_04, 1_05, 1_06, 1_07, 1_08, 1_09, 1_10, 1_11, 1_12, 1_13, 1_14, 1_15, 1_16, 1_17, 1_18, 1_19, 1_20, 1_21, 1_22, 1_23, 1_24 |
Sub2 | 0_01, 0_02, 0_03, 1_04, 1_05, 1_06, 1_07, 1_08, 1_09, 1_10, 1_11, 1_12, 1_13, 1_14, 1_15, 1_16, 1_17, 1_18, 1_19, 1_20, 1_21, 1_22, 1_23, 1_24, 2_25, 2_26, 2_27, 2_28, 2_29, 2_30, 2_31, 2_32, 2_33, 2_34, 2_35, 2_36, 2_37, 2_38, 2_39, 2_40, 2_41, 2_42, 2_43, 2_44 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
0_01 | AC | 1 ms | 256 KB |
0_02 | AC | 2 ms | 2940 KB |
0_03 | AC | 315 ms | 201084 KB |
1_04 | AC | 1 ms | 256 KB |
1_05 | AC | 2 ms | 3068 KB |
1_06 | AC | 2 ms | 2940 KB |
1_07 | AC | 2 ms | 1532 KB |
1_08 | AC | 2 ms | 1532 KB |
1_09 | AC | 2 ms | 1532 KB |
1_10 | AC | 2 ms | 1532 KB |
1_11 | AC | 2 ms | 1532 KB |
1_12 | AC | 2 ms | 3452 KB |
1_13 | AC | 2 ms | 1532 KB |
1_14 | AC | 2 ms | 3452 KB |
1_15 | AC | 2 ms | 2428 KB |
1_16 | AC | 2 ms | 1532 KB |
1_17 | AC | 2 ms | 3452 KB |
1_18 | AC | 2 ms | 1532 KB |
1_19 | AC | 2 ms | 2684 KB |
1_20 | AC | 1 ms | 256 KB |
1_21 | AC | 1 ms | 636 KB |
1_22 | AC | 1 ms | 380 KB |
1_23 | AC | 2 ms | 2684 KB |
1_24 | AC | 1 ms | 764 KB |
2_25 | AC | 266 ms | 201596 KB |
2_26 | AC | 261 ms | 201084 KB |
2_27 | AC | 217 ms | 201980 KB |
2_28 | AC | 80 ms | 201980 KB |
2_29 | AC | 79 ms | 201084 KB |
2_30 | AC | 247 ms | 202876 KB |
2_31 | AC | 210 ms | 202876 KB |
2_32 | AC | 244 ms | 202108 KB |
2_33 | AC | 98 ms | 202108 KB |
2_34 | AC | 202 ms | 202748 KB |
2_35 | AC | 208 ms | 202236 KB |
2_36 | AC | 94 ms | 202108 KB |
2_37 | AC | 163 ms | 201852 KB |
2_38 | AC | 197 ms | 201596 KB |
2_39 | AC | 147 ms | 202236 KB |
2_40 | AC | 104 ms | 161148 KB |
2_41 | AC | 97 ms | 89852 KB |
2_42 | AC | 216 ms | 196732 KB |
2_43 | AC | 133 ms | 117500 KB |
2_44 | AC | 3 ms | 5372 KB |