18163번 - Binary Matrix 서브태스크

키파는 율이로부터 0과 1이 가득한 n by n 표를 하나 선물로 받았습니다. 이 선물이 고마운 키파는 이 표를 커다란 행렬로 보고 K라는 이름을 붙여 주었습니다. 키파는 이 행렬을 가지고 놀아보기로 했습니다. 키파는 K의 각 성분이 0 혹은 1이라는 게 너무 마음에 든 나머지, 어떤 연산을 했을 때 계산 결과도 각 성분별로 짝수이면 0, 홀수이면 1을 채우기로 했습니다.

먼저 덧셈을 이용해서 K, K+K, K+K+K를 계산해 보다가 금방 싫증이 났습니다. K+K가 모든 성분이 0이어서 재미가 없었기 때문입니다. 그래서 곱셈을 하기로 했습니다. K, K², K³, ...을 계산하다가 어느 순간 똑같은 계산을 반복하고 있는 것 같았습니다!

같은 것을 반복하는 건 컴퓨터가 해야지 내가 하면 재미없다는 생각이 들었던 키파는, K를 가지고 곱셈을 하다가 언제 싫증이 날지가 궁금해졌습니다. 키파가 예전 계산 결과를 다시 보게 될 때 이 곱셈 식에 K가 몇 번 곱해져 있는지를 출력하는 프로그램을 작성해서 키파를 도와 줍시다.

첫째 줄에 행렬의 크기 n이 주어집니다.

둘째 줄부터 n개의 줄에 총 n개의 수가 공백을 사이에 두고 주어집니다. 이 수들은 모두 0 혹은 1입니다.

키파가 예전 계산 결과를 다시 보게 될 때 그 곱셈 식에 곱해진 K의 개수를 출력합니다.

n = 4.

n ≤ 128이며, 정답을 N이라 하면, K^N의 모든 성분은 0입니다.

n ≤ 8이며, K는 가역 행렬입니다.

n ≤ 8.

n ≤ 64.

n ≤ 128.

수학적으로 엄밀하게 설명해서 문제를 요약하면, 행렬 K가 주어지면, 자연수 집합의 부분집합

{n : ∃m, 1 ≤ m < n and K^m = Kⁿ}

의 최소 원소를 출력하는 문제입니다.