10830

백준 10830 풀이 (행렬 제곱, 분할 정복, 거듭제곱)

이번 문제는 이전문제들을 이용하여 풀면 아주 쉽게 풀 수 있다. 1. 분할 정복을 이용하여 거듭제곱을 구할수 있다. 2. 행렬제곱을 구할수 있다. 이 2가지가 가능하면 상당히 쉬운 문제이다. 그런데 정답률이 낮고 solved.ac에서 골드4인것은 좀 의문이다. 문제를 보면 행렬에 대해서 제곱을 하는 문제이다. 행렬을 제곱한다는것은 같은 놈을 여러번 곱한다는 소리다. 만약 행렬을 A라고 한다면 분할 정복을 이용하여 n을 아주 빠르게 구할 수 있다. $$ A^n = A^{n/2}*A^{n/2}$$ $$ A^{n/2}=A^{n/4}*A^{n/4}$$ 위의 식을 이용하면 분할하여 빠르게 A의 n승 행렬을 구할수 있다. 단, n이 홀수인 경우에는 n이 정확히 나누어 떨어지지 않기 때문에 $$ A^n = A^{n/..