14556번: Balance

https://www.acmicpc.net/problem/14556

$O(n)$

어떤 추의 무게는 그보다 가벼운 모든 추의 무게합보다 크다.
n개 추를 놓는 순서의 경우의 수를 an이라하자.
an+1은 마지막에 놓는 추의 종류에 따라 다음과 같은 경우로 나누어 계산할 수 있다.
1) 2^N+1 추를 오른쪽에 놓는다. -> an
2) 2^i (i<=N) 추를 왼쪽 혹은 오른쪽에 놓는다. -> an * 2N
따라서 an+1 = (2n+1) an
a1 = 1 이므로
an = 1 * 3 * 5 * ... * (2n-3) * (2n-1) 이다.

#include<cstdio>
int n, r = 1;
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) r = (1LL * r*(2 * i - 1)) % (int(1e9) + 9);
    printf("%d", r);
    return 0;
}