백준 27318번: 세상에서 가장 달달한 디저트 만들기 (integer)

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

27318번: 세상에서 가장 달달한 디저트 만들기

---

행렬 거듭제곱이 더 떠올리기 쉬운 풀이같긴 한데, 일반항을 구해서 풀 수 있는 문제이므로 일반항을 구하는 방법도 소개합니다.

 

이 글에서

$$V(N,M) = (12N-16)^{M}$$

이고

$$S(N,M) = (4N-4) \times S(N,M-1) + (24N-48) \times V(N,M-1)$$

이라는 걸 이미 설명했으니, 해당 지점부터 이어가겠습니다. 덧붙여,

$$V(N,0) = 1$$

$$S(N,0) = 6$$

을 가정합니다.

 

이때 $T(N,M) = \frac{S(N,M)}{(4N-4)^{M}}$을 도입하면, $S(N,M)$에 관한 점화식을 다음과 같이 볼 수 있습니다.

$$T(N,M) = T(N,M-1) + \frac{24N-48}{4N-4} \times \left ( \frac{12N-16}{4N-4} \right )^{M-1}$$

이로부터 다음을 얻습니다

$$T(N,M) = T(N,0) + \frac{24N-48}{4N-4} \times \left \{ \left ( \frac{12N-16}{4N-4} \right )^{0} + \left ( \frac{12N-16}{4N-4} \right )^{1} + \cdots + \left ( \frac{12N-16}{4N-4} \right )^{M-1} \right \}$$

등비수열의 합 공식을 적용하면

$$T(N,M) = T(N,0) + \frac{24N-48}{4N-4} \times \frac{\left ( \frac{12N-16}{4N-4} \right )^{M} - 1}{\frac{12N-16}{4N-4} - 1}$$

그런데 정의로부터 $T(N,0) = S(N,0) = 6$이므로 대입하여 식을 정리하면

$$\frac{S(N,M)}{(4N-4)^{M}} = 6 + \frac{24N-48}{(12N-16)-(4N-4)} \times \left \{ \left ( \frac{12N-16}{4N-4} \right )^{M} - 1 \right \}$$

이로부터 $S(N,M)$의 일반항은 다음과 같이 나타납니다.

$$S(N,M) = 6 \times (4N-4)^{M} + \frac{24N-48}{(12N-16)-(4N-4)} \times \left \{ (12N-16)^{M} - (4N-4)^{M} \right \}$$

뺄셈이 있으므로 적절하게 주의하여 코드를 짜야 합니다. 혹시 이것보다 더 간단한 일반항이 있으면 알려주시면 감사하겠습니다. 다음은 제 코드입니다.

#include <stdio.h>
#define mod 1000000007

long long power_modular (long long X, long long Y);

long long getP (long long N) {return 4 * N - 4;}
long long getQ (long long N) {return 24 * N - 48;}
long long getR (long long N) {return 12 * N - 16;}
long long getS (long long N) {return 48 * N - 72;}

int main() {
	
	long long N, M;
	scanf("%lld %lld", &N, &M);
	
	long long P = getP(N);
	long long Q = getQ(N);
	long long R = getR(N);
	long long S = getS(N);
	
	long long surface_area = S * power_modular(P, M - 1) % mod;
	surface_area = (surface_area + (__int128)Q * R * power_modular(R - P, mod - 2) * (power_modular(R, M - 1) - power_modular(P, M - 1) + mod)) % mod;
	
	long long volume = power_modular(R, M);
	
	printf("%lld %lld", volume, surface_area);
	return 0;
}

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

(C11, 0ms, 1116KB, 제출번호 57429393)

---