시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 1024 MB | 80 | 17 | 10 | 52.632% |
$n \times n$ 행렬 $A$의 행렬식(determinant) $\det A$는 아래와 같이 정의한다. 아래 식에서 $a_{ij}$는 $A$의 $i$행 $j$열에 위치한 원소를 나타낸다. 또한 $S_{n}$는 $\{1, \cdots, n\}$의 순열들의 집합으로, 각 $\sigma \in S_{n}$에 대해 $\{1, \cdots, n\} = \{\sigma(1), \cdots, \sigma(n)\}$을 만족한다.
$$ \det A = \sum_{\sigma \in S_{n}} \mathrm{sgn}(\sigma) \cdot \left(\prod_{i = 1}^{n} a_{i \sigma(i)}\right) $$
$A$의 characteristic polynomial $\phi_{A}(x)$는 $x$에 대한 $n$차 다항식으로, $\phi_{A}(x) = \det(x I - A) = c_{n}x^{n} + c_{n-1}x^{n-1} + \cdots + c_{0}$로 정의한다.
각 원소가 $0$ 이상 $10^{9}$ 미만의 정수인 행렬 $A$가 주어진다. 이 때 $\phi_{A}(x)$의 계수 $c_{0}, \cdots, c_{n}$ 또한 정수임을 증명할 수 있다. 주어진 정수 $M$에 대해, 이들을 각각 $M$으로 나눈 나머지를 구하는 프로그램을 작성하시오.
입력의 첫 줄에 행렬의 크기를 나타내는 정수 $n$과 나눗셈에 사용되는 정수 $M$이 주어진다.
둘째 줄부터 $n$개의 줄에 걸쳐 행렬 $A$의 원소가 각 줄에 $n$개씩 공백으로 구분지어 주어진다. 이 중 $i$번째 줄의 $j$번째 수는 $A$의 $i$행 $j$열의 원소 $a_{ij}$를 의미한다.
$n+1$개의 줄에 걸쳐 $c_{0}, \cdots, c_{n}$을 $M$으로 나눈 나머지를 출력한다.
정수 $a$를 $M$으로 나눈 나머지란, $a - b$가 $M$의 배수가 되는 가장 작은 음 아닌 정수 $b$를 의미한다.
2 100 2 1 4 3
2 95 1
$\phi_{A}(x) = (x-2)(x-3) - 4 = x^{2} - 5x + 2$이다.
5 200 3 1 4 1 5 9 2 6 5 3 5 7 9 8 9 3 2 3 8 4 6 2 6 4 3
160 79 94 15 175 1