Submission #1187381
Source Code Expand
#include <iostream> #include <vector> using namespace std; typedef long long ll; const ll MOD = 1000000007; ll pot(ll a, ll b) { if (b == 1) return a; if (b % 2 == 1) return a * pot(a, b - 1) % MOD; ll x = pot(a, b / 2); return x * x % MOD; } ll inv(ll a) { return pot(a, MOD - 2); } int main() { ios_base::sync_with_stdio(0); int n; string nap; cin >> n >> nap; int l = nap.size(); if (n < l) { cout << "0"; return 0; } vector< vector<ll> > dp(n + 1, vector<ll>(n + 1, 0)); dp[0][0] = 1; for (int i = 1; i < n + 1; ++i) { for (int j = 0; j < i + 1; ++j) { if (j - 1 >= 0) dp[i][j] = (dp[i][j] + 2 * dp[i - 1][j - 1]) % MOD; if (j + 1 <= n && j + 1 <= i - 1) dp[i][j] = (dp[i][j] + dp[i - 1][j + 1]) % MOD; if (j == 0) dp[i][j] = (dp[i][j] + dp[i - 1][j]) % MOD; } } ll odp = dp[n][l] * inv(pot(2, l)) % MOD; cout << odp; return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - Unhappy Hacking |
User | ArturSocha |
Language | C++14 (GCC 5.4.1) |
Score | 800 |
Code Size | 1118 Byte |
Status | AC |
Exec Time | 156 ms |
Memory | 195840 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 | 1024 KB |
0_03 | AC | 155 ms | 195840 KB |
1_04 | AC | 1 ms | 256 KB |
1_05 | AC | 2 ms | 1024 KB |
1_06 | AC | 2 ms | 1024 KB |
1_07 | AC | 2 ms | 1024 KB |
1_08 | AC | 2 ms | 1024 KB |
1_09 | AC | 2 ms | 1024 KB |
1_10 | AC | 2 ms | 1024 KB |
1_11 | AC | 2 ms | 1024 KB |
1_12 | AC | 2 ms | 1024 KB |
1_13 | AC | 2 ms | 1024 KB |
1_14 | AC | 2 ms | 1024 KB |
1_15 | AC | 2 ms | 1024 KB |
1_16 | AC | 2 ms | 1024 KB |
1_17 | AC | 2 ms | 896 KB |
1_18 | AC | 2 ms | 896 KB |
1_19 | AC | 2 ms | 896 KB |
1_20 | AC | 1 ms | 256 KB |
1_21 | AC | 1 ms | 640 KB |
1_22 | AC | 1 ms | 256 KB |
1_23 | AC | 2 ms | 896 KB |
1_24 | AC | 2 ms | 768 KB |
2_25 | AC | 155 ms | 195840 KB |
2_26 | AC | 156 ms | 195840 KB |
2_27 | AC | 154 ms | 195840 KB |
2_28 | AC | 155 ms | 195840 KB |
2_29 | AC | 155 ms | 195840 KB |
2_30 | AC | 155 ms | 195840 KB |
2_31 | AC | 155 ms | 195840 KB |
2_32 | AC | 155 ms | 195840 KB |
2_33 | AC | 155 ms | 195840 KB |
2_34 | AC | 155 ms | 195840 KB |
2_35 | AC | 154 ms | 195712 KB |
2_36 | AC | 155 ms | 195328 KB |
2_37 | AC | 154 ms | 195328 KB |
2_38 | AC | 154 ms | 195328 KB |
2_39 | AC | 155 ms | 195456 KB |
2_40 | AC | 123 ms | 154880 KB |
2_41 | AC | 64 ms | 79360 KB |
2_42 | AC | 147 ms | 185600 KB |
2_43 | AC | 81 ms | 100864 KB |
2_44 | AC | 4 ms | 3328 KB |