백준 30521번: Mike Sees The Storm (Large)

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

30521번: Mike Sees The Storm (Large)

---

카탈란 수의 응용입니다.

 

먼저 주어진 문제를 격자 속의 최단 경로 문제로 환원합니다.

 

칠판에 적힌 숫자를 $a$에서 $a-1$ 로 바꾸는 연산을 오른쪽으로 한 칸 이동하는 것으로,

$a$에서 $a+1$로 바꾸는 연산을 위로 한 칸 이동하는 것으로 간주할 수 있습니다.

 

이렇게 문제를 환원하였을 때 최댓값이 0인 경로는 주대각선의 아래로만 지나가는 경로임을 확인할 수 있습니다.

 

또한 그러한 경로의 개수는 카탈란 수와 같은데, 이는 대각선을 지나는 경로를 대칭시키는 방법으로 구할 수 있습니다.

 

결과적으로 최댓값이 $0$ 인 경로의 개수는

$$\binom{2N}{N} - \binom{2N}{N-1}$$

입니다.

 

이제 최댓값이 $1$ 인 경로의 개수를 구합니다.

 

카탈란 수를 구할 때와 마찬가지로 대각선을 설정한 뒤, 해당 대각선을 지나는 경로를 대칭시킵니다.

 

그러면 최댓값이 $1$ 인 경로의 개수는

$$\binom{2N}{N} - \binom{2N}{N-2} - \left \{ \binom{2N}{N} - \binom{2N}{N-1} \right \}$$

$$= \binom{2N}{N-1} - \binom{2N}{N-2}$$

와 같이 나오게 됩니다.

 

이런 식으로 최댓값이 $i$ 인 경로의 개수가 다음과 같이 나옵니다.

$$\binom{2N}{N - i} - \binom{2N}{N - i - 1}$$

이로부터 정답은

$$N^{k} + \sum_{i=0}^{N-1}i^{k} \times \left \{ \binom{2N}{N - i} - \binom{2N}{N - i - 1} \right \}$$

인데, 식을 변형하여

$$\sum_{i=0}^{N-1} \binom{2N}{i} \left \{ (N-i)^{K} - (N-i-1)^{K} \right \}$$

으로도 구할 수 있습니다.

 

이론상 최선의 시간복잡도는 $O(N \log K)$ 이지만, $O(N \log P + N \log K)$ 로도 시간 안에 충분히 들어옵니다.

 

제 코드는 다음과 같습니다.

#include <stdio.h>
#define mod 1000000007ull
typedef unsigned long long ull;

ull power_modular (ull X, ull Y) {
	ull result = 1;
	while(Y) {
		if (Y % 2) {
			result = result * X % mod;
		}
		X = X * X % mod;
		Y /= 2;
	}
	return result;
}

int main() {
	
	ull N, K;
	scanf("%llu %llu", &N, &K);
	
	ull array[1000001] = {};
	for (int i = 0; i <= N; i++) array[i] = power_modular(i, K);
	
	ull answer = 0;
	ull binom = 1;
	for (int i = 0; i < N; i++) {
		answer = (answer + binom * (array[N - i] - array[N - 1 - i] + mod)) % mod;
		binom = (binom * (2 * N - i) % mod) * power_modular(i + 1, mod - 2) % mod;
	}
	
	printf("%llu", answer);
	return 0;
}

(C11, 184ms, 8808KB, 제출번호 69530647)

---

$O(N\log P \log K)$ 로도 풀릴까요?