이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |