행렬을 이용한 $N$ 거듭제곱은 **‘정확히 $N$번 만에 $i$→$j$로 이동 가능한 경로의 수’**를 의미한다.
특이점은, 2차원 배열을 표현하기 위해 사용한 vector<vector<int>> 타입과 재귀호출을 사용한 코드는 시간초과, 메모리초과가 발생했다.
재귀호출 구문을 반복문으로 변경하고, vector<vector<int>>가 아닌 vector<int> 타입을 써서 $i*N+j$ 인덱스로 접근하도록 구현하니, 정적배열 + 반복문을 쓸 때와 동일한 속도와 더 적은 메모리로 풀이 가능했다.
고민해보니 vector<vector<int>> 형태는 메모리상에 배열이 matrix 모양으로 존재하는 게 아니다. vectror<> 자료구조를 나열한 것이기 때문에, 정확히 직사각형으로 배열의 메모리가 존재할 수 없다. 그렇기에 vector<>에서 정적배열처럼 2차원 배열의 구조를 쓰고 싶으면, 1차원으로 선언하고 인덱스를 bijection하는 방법으로 접근해야 한다.
동적 배열을 쓸 때의 장점은 배열을 함수의 반환으로 사용 가능하다는 점이다. 정적 배열로 값을 반환하려면, 함수의 인자로 *outData를 받아서 값을 전달해야 한다. 이렇게 하면 인자도 많아지고 코드도 길어지고 가독성도 해치게 되어 최종적으로는 동적 배열을 사용하는 코드를 채택했다.