問題一覧 > 通常問題

No.2255 Determinant Sum

レベル : / AI推定難易度 : 1950 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 42
作問者 : shobonvip / テスター : noya2 👑 Nachia
お気に入りにしたユーザー ProblemId : 9052 / 自分の提出
問題文最終更新日: 2023-03-24 04:35:24
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 382 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。