AtCoder Regular Contest 059

Submission #839457

Source codeソースコード

#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

Task問題 F - バイナリハック / Unhappy Hacking
User nameユーザ名 math
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 800
Source lengthソースコード長 3116 Byte
File nameファイル名
Exec time実行時間 7 ms
Memory usageメモリ使用量 640 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - 0_01,0_02,0_03
Sub1 400 / 400 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 400 / 400 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
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