Submission #839457
Source Code Expand
#include <bits/stdc++.h> using namespace std; #define FOR(i,n) for(int i = 0; i < (n); i++) #define sz(c) ((int)c.size()) #define ten(n) ((int)1e##n) using ll = long long; const int MOD = ten(9) + 7; const int N = ten(4); // O(N) ll inverse[N]; void init_inverse() { inverse[1] = 1; for (int i = 2; i < N; i++) inverse[i] = (MOD - MOD / i) * inverse[MOD%i] % MOD; } // O(N) ll fact[N], infact[N]; void init_fast_fact() { init_inverse(); fact[0] = fact[1] = 1; for (int i = 2; i < N; i++) fact[i] = fact[i - 1] * i % MOD; infact[0] = infact[1] = 1; for (int i = 2; i < N; i++) infact[i] = infact[i - 1] * inverse[i] % MOD; } // O(1) ll fast_nCk(int n, int k) { if (n < 0 || k < 0) return 0; if (k > n) return 0; ll ret = fact[n] * infact[k] % MOD * infact[n - k] % MOD; return ret; } //O(1) ll pseudo_catalan(int a, int b, int c) { if (c == a - 1) b--, c--; if (c == b - 1) a--, c--; ll ret = fast_nCk(a + b - 2, a - 1) - fast_nCk(a + b - 2, c - 1); if (ret < 0) ret += MOD; return ret; } int solve(int n, int m) { // O(n) にできるが、今回は十分に大きい定数回回している init_fast_fact(); // https://oeis.org/A126087 // magic[i] = i回タイプした時、文字列が空になるようなキーの押し方の個数 // O(n) vector<ll> magic = { 1, 1, 3 }; for (int i = 3; i <= n; i++) { ll tmp = 3 * (i + 1) * magic[i - 1] + 8 * (i - 2) * magic[i - 2] - 24 * (i - 2) * magic[i - 3]; magic.push_back(tmp % MOD * inverse[i + 1] % MOD); if (magic[i] < 0) magic[i] += MOD; } // 2の累乗 // O(n) vector<ll> power_of_2; power_of_2.push_back(1); FOR(i, n) power_of_2.push_back(power_of_2.back() * 2 % MOD); ll ans = 0; FOR(s, n) { // ループ内はO(1) // // |------|X|-------| // <------>^<-------> // | | | // s | rem - 1 // s回目(0-indexed) // // 前半s回のタイプ後、文字列の長さが0 // s+1回目、最初の文字を打つ // 後半、s+2回目以降は、文字列が空にならないよう注意しながらタイピング // こうすると重複せず数え上げられる // // 前半はmagicに係数が入っているので、後半のs+2回目以降のタイプの仕方について数え上げればよい const int rem = n - s; //後 rem 回タイプ出来る if (rem < m) continue; if ((rem - m) % 2 != 0) continue; const int B = (rem - m) / 2; // s+2回目以降のバックスペースの回数 const int A = rem - B; // s+2回目以降タイプする文字列 (= {0,1}をタイプする回数) const ll a1 = B == 0 ? 1 : pseudo_catalan(A , B + 1, B); //カタラン数の計算方法と同じやつ // バックスペースで消される文字列は{0,1}のどっちでもいいので、 2^B を掛ける const ll s_ans = a1 * power_of_2[B] % MOD * magic[s] % MOD; ans += s_ans; } return int(ans % MOD); } int main() { int n; cin >> n; string s; cin >> s; int m = sz(s); int ans = solve(n, m); cout << ans << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - Unhappy Hacking |
User | math |
Language | C++14 (GCC 5.4.1) |
Score | 800 |
Code Size | 3116 Byte |
Status | AC |
Exec Time | 7 ms |
Memory | 640 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 | 5 ms | 512 KB |
0_02 | AC | 5 ms | 512 KB |
0_03 | AC | 6 ms | 640 KB |
1_04 | AC | 5 ms | 512 KB |
1_05 | AC | 5 ms | 512 KB |
1_06 | AC | 5 ms | 512 KB |
1_07 | AC | 5 ms | 512 KB |
1_08 | AC | 5 ms | 512 KB |
1_09 | AC | 5 ms | 512 KB |
1_10 | AC | 5 ms | 512 KB |
1_11 | AC | 5 ms | 512 KB |
1_12 | AC | 7 ms | 512 KB |
1_13 | AC | 5 ms | 512 KB |
1_14 | AC | 5 ms | 512 KB |
1_15 | AC | 5 ms | 512 KB |
1_16 | AC | 5 ms | 512 KB |
1_17 | AC | 5 ms | 512 KB |
1_18 | AC | 5 ms | 512 KB |
1_19 | AC | 5 ms | 512 KB |
1_20 | AC | 5 ms | 512 KB |
1_21 | AC | 5 ms | 512 KB |
1_22 | AC | 5 ms | 512 KB |
1_23 | AC | 5 ms | 512 KB |
1_24 | AC | 5 ms | 512 KB |
2_25 | AC | 6 ms | 640 KB |
2_26 | AC | 5 ms | 640 KB |
2_27 | AC | 6 ms | 640 KB |
2_28 | AC | 6 ms | 640 KB |
2_29 | AC | 6 ms | 640 KB |
2_30 | AC | 6 ms | 640 KB |
2_31 | AC | 6 ms | 640 KB |
2_32 | AC | 6 ms | 640 KB |
2_33 | AC | 6 ms | 640 KB |
2_34 | AC | 6 ms | 640 KB |
2_35 | AC | 6 ms | 640 KB |
2_36 | AC | 6 ms | 640 KB |
2_37 | AC | 6 ms | 640 KB |
2_38 | AC | 6 ms | 640 KB |
2_39 | AC | 6 ms | 640 KB |
2_40 | AC | 6 ms | 640 KB |
2_41 | AC | 5 ms | 640 KB |
2_42 | AC | 6 ms | 640 KB |
2_43 | AC | 5 ms | 640 KB |
2_44 | AC | 5 ms | 512 KB |