https://www.acmicpc.net/problem/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)
'분할 정복을 이용한 거듭제곱 > 정수 거듭제곱' 카테고리의 다른 글
백준 28294번: 프랙탈 (0) | 2023.09.02 |
---|---|
백준 27875번: 파이파이 (0) | 2023.09.01 |
백준 25028번: Fully Generate (0) | 2023.03.10 |
백준 18151번: DivModulo (0) | 2023.02.28 |
백준 10909번: Quaternion inverse (0) | 2023.02.14 |