| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 19767 |
2016-02-25T05:24:27 Z |
Qwaz |
괄호 (kriii4_R) |
C++14 |
|
137 ms |
1084 KB |
#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;
}
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
