시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
0.5 초 512 MB 131 13 6 100.000%

문제

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

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

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

입력

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

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

출력

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

서브태스크 1 (2점)

n = 4.

서브태스크 2 (3점)

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

서브태스크 3 (3점)

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

서브태스크 4 (12점)

n ≤ 8.

서브태스크 5 (60점)

n ≤ 64.

서브태스크 6 (20점)

n ≤ 128.

예제 입력 1

4
0 1 1 1
1 0 1 1
0 0 0 1
0 1 0 0

예제 출력 1

5

예제 입력 2

16
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 1 0 1 0 1 1 1 1 1 0 1 0 0
0 0 0 1 0 1 0 0 1 0 1 0 0 1 0 0
0 1 1 1 0 1 0 0 1 0 1 0 0 1 1 0
0 0 0 1 0 1 0 0 1 0 1 0 0 1 0 0
0 1 1 0 0 1 0 1 1 1 1 1 0 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 1 0 1 0 0 0 1 0 0 0 0
0 0 1 0 0 1 1 1 0 1 1 1 1 1 0 0
0 1 0 1 0 1 0 1 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 0
0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 1 0 1 1 1 1 1 1 1 0
0 0 1 1 1 1 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0

예제 출력 2

514

노트

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

{n : ∃m, 1 ≤ m < n and Km = Kn}

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

출처

Contest > 키파컵 > 제2회 키파컵 B번

  • 문제를 만든 사람: kipa00

채점

  • 예제는 채점하지 않는다.