30103번 - 어려운 선형대수학 문제

$Z_{998244353}$에서 정의되는 $n \times n$ 크기의 두 가역행렬 $A$, $B$의 친화도는 다음 조건에 맞는 $i$ ($1 \le i \le n$)의 개수이다.

• $A$의 $i$번째 열, $B$의 $i$번째 열을 맞바꾸었을 때, $A$와 $B$가 모두 가역행렬이다.

즉, 친화도는 $0$ 이상 $n$ 이하의 정수이다.

행렬 $A_i$를 행렬 $A_{i-1}$의 제일 왼쪽 열을 제일 오른쪽으로 옮긴 행렬로 정의하자. 이때 $A_0 = A$이다.

$0$이상 $N$ 미만의 정수 $i$에 대하여, $A_i$와 $B$의 친화도를 구하자.

첫 줄에 양의 정수 $n$이 주어진다.

두 번째 줄부터 총 $n$개의 줄에 걸쳐 행렬 $A$에 대한 정보가 입력된다. 각 $n$개의 줄에는 $n$개의 정수가 공백으로 구분되어 있으며, $(i+1)$번째 줄의 $j$번째 정수는 $A_{ij}$를 의미한다.

$n+2$ 번째 줄부터 총 $n$개의 줄에 걸쳐 행렬 $B$에 대한 정보가 입력된다. 각 $n$개의 줄에는 $n$개의 정수가 공백으로 구분되어 있으며, $(i+n+1)$번째 줄의 $j$번째 정수는 $B_{ij}$를 의미한다.

첫 줄에 $n$개의 정수를 공백을 사이에 두고 출력하라. $i+1$번째로 출력해야 할 정수는 $A_i$와 $B$의 친화도이다.

• $2 \le n \le 200$
• 행렬의 각 성분은 $0$ 이상 $998244352$ 이하의 정수이다.
• $A$와 $B$는 가역행렬이다.