취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 28294번 문제인 프랙탈이다.
문제는 아래 링크를 확인하자.

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

한 변의 길이가 \(N^a\)인 정\(N\)각형에 문제에서 주어진 작업을 \(k\)번 반복한 도형의, 다음 작업때 변형되는 에지의 개수를 \(e_{N,a}\), 둘레의 길이를 \(l_{N,a}\)라 하자.

이 때 다음 두 식이 성립함을 관찰하자.

\(e_{N,a+1} = (N-1)e_{N,a}\)

\(l_{N,a+1} = (N-2)e_{N,a} + (N-1)l_{N,a}\)

첫 식은 변형되는 에지마다 \(N\)각형 모양이 하나씩 생기는 것을 관찰하는 것으로, 두 번째 식은 먼저 기존 도형을 \(N\)배 확대한 다음 추가되는 길이 \((N-1)e_{N,a}\) 및 지워지는 길이 \(e_{N,a}\)를 관찰하는 것으로 간단히 세울 수 있다.

위 점화관계를 행렬로 표현한 뒤, binary exponentiaion을 이용해 문제의 답 \(l_{N,a}\)을 계산하는 것으로 문제를 해결하자.

아래는 제출한 소스코드이다.

#define MOD 1000000007
#include <iostream>
using namespace std;
typedef long long ll;

ll N, a;
ll mat[2][2], vec[2];
ll tmp[2][2], vtmp[2];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> a;
	mat[0][0] = N - 1, mat[1][0] = N - 2, mat[1][1] = N, vec[0] = N, vec[1] = N;

	while (a) {
		if (a & 1) {
			vtmp[0] = mat[0][0] * vec[0] + mat[0][1] * vec[1];
			vtmp[1] = mat[1][0] * vec[0] + mat[1][1] * vec[1];
			vec[0] = vtmp[0] % MOD, vec[1] = vtmp[1] % MOD;
		}
		tmp[0][0] = mat[0][0] * mat[0][0] + mat[0][1] * mat[1][0];
		tmp[0][1] = mat[0][0] * mat[0][1] + mat[0][1] * mat[1][1];
		tmp[1][0] = mat[1][0] * mat[0][0] + mat[1][1] * mat[1][0];
		tmp[1][1] = mat[1][0] * mat[0][1] + mat[1][1] * mat[1][1];

		mat[0][0] = tmp[0][0] % MOD;
		mat[0][1] = tmp[0][1] % MOD;
		mat[1][0] = tmp[1][0] % MOD;
		mat[1][1] = tmp[1][1] % MOD;

		a >>= 1;
	}

	cout << vec[1];
}