백준 28294번: 프랙탈

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

28294번: 프랙탈

---

단계별로 도형의 둘레를 구해보며 접근하면 규칙이 바로 나오는 문제입니다.

 

아무 과정도 거치지 않은 상태의 둘레의 길이는 $N \times N^{a}$ 입니다.

 

그 다음, 한 변이 $N^{a-1}$인 도형을 그리면, 증가하는 둘레의 길이는 $N \times (N-2)N^{a-1}$ 입니다.

 

3단계에서 증가하는 둘레의 길이는 $N \times (N-1) \times (N-2)N^{a-2}$ 입니다.

 

4단계에서 증가하는 둘레의 길이는 $N \times (N-1)^{2} \times (N-2)N^{a-3}$ 입니다.

 

즉, 최종적인 둘레의 길이가 다음과 같습니다.

$$ N \times N^{a} + N \times (N-2)N^{a-1} + N \times (N-1) \times (N-2)N^{a-2} + N \times (N-1)^{2} \times (N-2)N^{a-3} + \cdots + N \times (N-1)^{a-1} \times (N-2)N^{0} $$

이제 식을 정리합니다. 둘레의 길이가 $F(N,a)$ 일 때

$$ F(N,a) = N \times N^{a} + N(N-2)\left \{ N^{a-1} + (N-1) \times N^{a-2} + \cdots + (N-1)^{a-1} \right \}$$

$$ = N \times N^{a} + N(N-2) \times \frac{N^{a-1}\left \{ 1 - \left ( \frac{N-1}{N} \right )^{a} \right \}}{1 - \frac{N-1}{N}}$$

$$ = N^{a+1} + (N-2) \times N^{a+1} \left \{ 1 - \frac{(N-1)^{a}}{N^{a}} \right \}$$

$$ = (N-1)N^{a+1} - N(N-2)(N-1)^{a} $$

$$ = (N-1)\left \{ N^{a+1} - (N-1)^{a+1} \right \} + (N-1)^{a} $$

이는 Bianry Exponentiation으로 $O(\log N)$에 구할 수 있습니다. 음수 모듈러 연산에 주의해야 합니다.

 

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

#include <stdio.h>
#define mod 1000000007

long long power_modular (long long x, long long y);

int main() {
	
	int N, a;
	scanf("%d %d", &N, &a);
	
	long long answer = (power_modular(N-1, a) +
	                    (N-1) * (power_modular(N, a+1) - power_modular(N-1, a+1) + mod)) % mod;

	printf("%lld", answer);
	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, 제출번호 65338283)

---

뭔가 더 예쁘게 식 정리를 하고 싶었는데, 이 정도가 제 한계였습니다.