행렬의 거듭 제곱( feat. 단위 행렬)

아래 문제에서 우리는 이진수를 사용하여, 거듭 제곱을 시간 복잡도 O(log N)으로 구하였다. 

https://jbluke.tistory.com/186

백준 11401번 ( 합동식 )

B=1;
// R! 구하기
    for(ll i = 1; i <= R; i++){
        B *= i;
        B %= MOD;
    }
    
    // R!(N-R)! 구하기
    for(ll i = 1; i <= N - R; i++){
        B *= i;
        B %= MOD;
    }

 

Q. 그럼 행렬의 거듭 제곱은 어떻게 구하면 될까??

A. 위 코드에서 B=1 부분이 있다. 

만약 행렬 A가 있다고 하자. 

행렬 A를 곱했을 때, 그 결과가 행렬 A로 나오게 하기 위해서는 어떤 행렬에 행렬A를 곱해야 할까??

단위 행렬을 만들면 된다. ( 단위 행렬 X 행렬 A = 행렬 A)

이 단위 행렬 이외에는, 정수의 거듭 제곱을 구하는 방법과 같다. 

( 아래 문제를 참고1)

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

10830번: 행렬 제곱