답안 #19767

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
19767	2016-02-25T05:24:27 Z	Qwaz	괄호 (kriii4_R)	C++14	100 / 100	137 ms	1084 KB

R

#include <cstdio>

typedef long long ll;
const int MOD = 1000000007;

ll modpow(ll a, ll x) {
	ll ret = 1;
	a = a % MOD;

	while (x) {
		if (x & 1) ret = ret * a % MOD;
		a = a * a % MOD;
		x >>= 1;
	}

	return ret;
}

int main() {
	int n, k;
	scanf("%d%d", &n, &k);

	ll res = 1, catalan = 1, xk = 1;
	for (int i = 2; i <= n+1; i++) {
		if (i & 1) {
			res = res * (k+1) % MOD;
		} else {
			res = (res * (k+1) - catalan * xk) % MOD;
			if (res < 0) res += MOD;

			int t = (i >> 1) - 1;
			catalan = 2 * (2*t + 1) * modpow(t+2, MOD-2) % MOD * catalan % MOD;
			xk = xk * k % MOD;
		}
	}

	printf("%lld\n", res);

	return 0;
}

Subtask #1

8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	42 ms	1084 KB	Output is correct
2	Correct	8 ms	1084 KB	Output is correct
3	Correct	101 ms	1084 KB	Output is correct
4	Correct	112 ms	1084 KB	Output is correct
5	Correct	114 ms	1084 KB	Output is correct
6	Correct	63 ms	1084 KB	Output is correct
7	Correct	71 ms	1084 KB	Output is correct
8	Correct	48 ms	1084 KB	Output is correct
9	Correct	20 ms	1084 KB	Output is correct
10	Correct	5 ms	1084 KB	Output is correct
11	Correct	5 ms	1084 KB	Output is correct
12	Correct	103 ms	1084 KB	Output is correct
13	Correct	97 ms	1084 KB	Output is correct
14	Correct	42 ms	1084 KB	Output is correct
15	Correct	46 ms	1084 KB	Output is correct
16	Correct	41 ms	1084 KB	Output is correct
17	Correct	125 ms	1084 KB	Output is correct
18	Correct	129 ms	1084 KB	Output is correct
19	Correct	137 ms	1084 KB	Output is correct
20	Correct	137 ms	1084 KB	Output is correct

Subtask #2

92.0 / 92.0

#	결과	실행 시간	메모리	Grader output
1	Correct	34 ms	1084 KB	Output is correct
2	Correct	12 ms	1084 KB	Output is correct
3	Correct	25 ms	1084 KB	Output is correct
4	Correct	120 ms	1084 KB	Output is correct
5	Correct	77 ms	1084 KB	Output is correct
6	Correct	95 ms	1084 KB	Output is correct
7	Correct	66 ms	1084 KB	Output is correct
8	Correct	38 ms	1084 KB	Output is correct
9	Correct	65 ms	1084 KB	Output is correct
10	Correct	9 ms	1084 KB	Output is correct
11	Correct	107 ms	1084 KB	Output is correct
12	Correct	112 ms	1084 KB	Output is correct
13	Correct	103 ms	1084 KB	Output is correct
14	Correct	50 ms	1084 KB	Output is correct
15	Correct	62 ms	1084 KB	Output is correct
16	Correct	63 ms	1084 KB	Output is correct
17	Correct	7 ms	1084 KB	Output is correct
18	Correct	136 ms	1084 KB	Output is correct
19	Correct	137 ms	1084 KB	Output is correct
20	Correct	136 ms	1084 KB	Output is correct