No.2255 Determinant Sum
Problem Statement
You are given a prime $P$. You are also given a square matrix $A$ of order $N$ as follows.
$$A = \begin{pmatrix} A_{1,1} & A_{1,2} & \cdots & A_{1,N}\\ A_{2,1} & A_{2,2} & \cdots & A_{2,N}\\ \vdots & \vdots & \ddots & \vdots\\ A_{N,1} & A_{N,2} & \cdots & A_{N,N} \end{pmatrix}$$
Each $A_{i,j}$ $(1 \le i, j \le N)$ is either $-1$ or an integer at least $0$ and less than $P$.
By changing each $-1$ contained in the matrix $A$ to an integer at least $0$ and less than $P$, one can obtain $P^M$ versions of $A$, where $M$ is the number of $-1$ contained in $A$.
For all of them, compute the determinant $\det A$ of $A$, and output the remainder (at least $0$ and less than $P$) when the sum of these determinants is divided by $P$.
Note that you are not asked for the sum of the remainders of $\det A$ divided by $P$.
Solve $T$ independent test cases.
Notes
What is a determinant? (Click to expand)
Let $N$ be a positive integer. For a permutation $\sigma = (\sigma_1, \sigma_2, \cdots, \sigma_N)$ of $(1, 2, \cdots, N)$, the inversion number of $\sigma$ is the number of pairs of integers $(i, j)$ satisfying $1 \le i < j \le N$ such that $\sigma_i > \sigma_j$.
Let $S_N$ be the set of all permutations of $(1, 2, \cdots, N)$. For $\sigma \in S_N$, the sign of the permutation $\mathrm{sgn} ~ \sigma$ is defined as follows: if the inversion number of $\sigma$ is even, then $\mathrm{sgn} ~ \sigma = 1$, and if it is odd, then $\mathrm{sgn} ~ \sigma = -1$.
Then, for a square matrix $A = (A_{i,j})$ of order $N$ consisting of real numbers, its determinant $\det A$ is defined as follows.
$$\det A = \sum_{\sigma \in S_N} \left\{(\mathrm{sgn} ~ \sigma) \prod_{i=1}^N A_{i, \sigma_i}\right \}$$
Here, $\displaystyle \sum_{P \in S_N}$ denotes the sum over all permutations $\sigma$ of $(1, 2, \cdots, N)$, and $\displaystyle \prod_{i=1}^N x_i$ denotes $x_1 \times x_2 \times \cdots \times x_N$. Although the determinant is defined this way here, this explanation may not be the usual one. However, this definition is equivalent to other definitions of the determinant.
The determinant $\det A$ of $\begin{pmatrix} 1 & 2\\ 3 & 4 \end{pmatrix}$ is $\det A = 1 \times 4 - 2 \times 3 = -2$, since $\mathrm{sgn}((1, 2)) = 1, \mathrm{sgn}((2, 1)) = -1$.
In the case $N=3$, the determinant $\det B$ of $B = \begin{pmatrix} 11 & 12 & 13\\ 21 & 22 & 23\\ 31 & 32 & 33 \end{pmatrix}$ is $\det B = 11 \times 22 \times 33 - 11 \times 23 \times 32 - 12 \times 21 \times 33 + 12 \times 23 \times 31 + 13 \times 21 \times 32 - 13 \times 22 \times 31 = 0$.
Constraints
- All inputs are integers
- $1 \le T \le 100$
- $2 \le N \le 50$
- $2 \le P \lt 10^9$
- $P$ is prime
- $-1 \le A_{i, j} < P$
- There exists at least $1$ pair $(i, j)$ such that $A_{i, j} = -1$
Input
The input is given from standard input in the following format. Here, $\mathrm{test}_{i}$ represents the $i$-th test case.$T$
$\mathrm{test}_1$
$\mathrm{test}_2$
$\vdots$
$\mathrm{test}_T$
Each test case is given in the following format.
$N$ $P$
$\begin{matrix}
A_{1,1} & A_{1,2} & \cdots & A_{1,N}\\
A_{2,1} & A_{2,2} & \cdots & A_{2,N}\\
\vdots & \vdots & \ddots & \vdots\\
A_{N,1} & A_{N,2} & \cdots & A_{N,N}
\end{matrix}$
Output
Print $T$ lines. On line $i$ $(1 \le i \le T)$, print the answer to the $i$-th test case.
Sample
Sample 1
Input
3 3 3 1 2 -1 -1 1 2 1 0 1 3 2 -1 0 0 0 -1 0 0 0 -1 4 998244353 0 0 0 0 0 -1 -1 -1 0 -1 -1 -1 0 -1 -1 -1
Output
0 1 0
In test case number $1$, the given matrix $A$ is as follows.
$$A= \begin{pmatrix} 1&2&-1\\-1&1&2\\1&0&1 \end{pmatrix}$$
There are $9$ matrices obtained by changing each $-1$ contained in the matrix $A$ to an integer at least $0$ and less than $3$, and for each of them we have
$\det \begin{pmatrix} 1&2&0\\0&1&2\\1&0&1 \end{pmatrix} = 5, \det \begin{pmatrix} 1&2&0\\1&1&2\\1&0&1 \end{pmatrix} = 3, \det \begin{pmatrix} 1&2&0\\2&1&2\\1&0&1 \end{pmatrix} = 1,$
$\det \begin{pmatrix} 1&2&1\\0&1&2\\1&0&1 \end{pmatrix} = 4, \det \begin{pmatrix} 1&2&1\\1&1&2\\1&0&1 \end{pmatrix} = 2, \det \begin{pmatrix} 1&2&1\\2&1&2\\1&0&1 \end{pmatrix} = 0,$
$\det \begin{pmatrix} 1&2&2\\0&1&2\\1&0&1 \end{pmatrix} = 3, \det \begin{pmatrix} 1&2&2\\1&1&2\\1&0&1 \end{pmatrix} = 1, \det \begin{pmatrix} 1&2&2\\2&1&2\\1&0&1 \end{pmatrix} = -1$
so the sum of the determinants is $5+3+1+4+2+0+3+1+(-1)=18$. The answer is $0$, the remainder when this is divided by $3$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
noya2
Nachia