No.2255 Determinant Sum
タグ : / 解いたユーザー数 40
作問者 :
shobonvip
/ テスター :
noya2
👑 
Nachia
問題文
素数 $P$ が与えられます。また、$N$ 次正方行列 $A$ が次のように与えられます。
$$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}$$
各 $A_{i,j}$ $(1 \le i, j \le N)$ は $-1$ もしくは $0$ 以上 $P$ 未満の整数です。
行列 $A$ に含まれる $-1$ のそれぞれを $0$ 以上 $P$ 未満の整数に変えることで得られる $A$ は、$A$ に含まれる $-1$ の数を $M$ 個として $P^M$ 個あります。
それら全てに対して $A$ の行列式 $\det A$ を求め、その総和を $P$ で割ったあまり（$0$ 以上 $P$ 未満）を答えてください。
$\det A$ を $P$ で割ったあまりの総和を答えるのではないことに注意してください。
$T$ 個の独立なテストケースについて答えを求めてください。
注記
行列式とは？ (クリックして展開)
$N$ を正整数とします。$(1, 2, \cdots, N)$ の順列 $\sigma = (\sigma_1, \sigma_2, \cdots, \sigma_N)$ に対して、 $\sigma$ の転倒数を $1 \le i < j \le N$ を満たす整数の組 $(i, j)$ であって $\sigma_i > \sigma_j$ を満たすものの個数とします。
$S_N$ を $(1, 2, \cdots, N)$ の順列全体の集合とし、$\sigma \in S_N$ に対して順列の符号 $\mathrm{sgn} ~ \sigma$ を、$\sigma$ の転倒数が偶数なら $\mathrm{sgn} ~ \sigma = 1$、奇数なら $\mathrm{sgn} ~ \sigma = -1$ と定めます。
このとき、実数からなる $N$ 次正方行列 $A = (A_{i,j})$ に対して、その行列式 $\det A$ を次のように定義します。
$$\det A = \sum_{\sigma \in S_N} \left\{(\mathrm{sgn} ~ \sigma) \prod_{i=1}^N A_{i, \sigma_i}\right \}$$
ここで、$\displaystyle \sum_{P \in S_N}$ とは $(1, 2, \cdots, N)$ の順列 $\sigma$ すべてについての和、$\displaystyle \prod_{i=1}^N x_i$ は $x_1 \times x_2 \times \cdots \times x_N$ を表します。なお、今回はこのように行列式を定義しておりますが、一般的ではない説明になっているかもしれません。ただし、この定義は他の行列式の定義と同値です。
$\begin{pmatrix} 1 & 2\\ 3 & 4 \end{pmatrix}$ の行列式 $\det A$ は、$\mathrm{sgn}((1, 2)) = 1, \mathrm{sgn}((2, 1)) = -1$ なので $\det A = 1 \times 4 - 2 \times 3 = -2$ となります。
$N=3$ の場合、$B = \begin{pmatrix} 11 & 12 & 13\\ 21 & 22 & 23\\ 31 & 32 & 33 \end{pmatrix}$ の行列式 $\det B$ は、$\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$ となります。
制約
- 入力はすべて整数
- $1 \le T \le 100$
- $2 \le N \le 50$
- $2 \le P \lt 10^9$
- $P$ は素数
- $-1 \le A_{i, j} < P$
- $A_{i, j} = -1$ となる $(i, j)$ の組が $1$ つ以上存在する
入力
入力は以下の形式で標準入力から与えられます。ここで、$\mathrm{test}_{i}$ は $i$ 番目のテストケースを表します。$T$
$\mathrm{test}_1$
$\mathrm{test}_2$
$\vdots$
$\mathrm{test}_T$
各テストケースは以下の形式で与えられます。
$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}$
出力
$T$ 行出力してください。$i$ $(1 \le i \le T)$ 行目には、$i$ 番目のテストケースに対する答えを出力してください。
サンプル
サンプル1
入力
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
出力
0 1 0
$1$ 番目のテストケースでは、与えられる行列 $A$ は次のようになります。
$$A= \begin{pmatrix} 1&2&-1\\-1&1&2\\1&0&1 \end{pmatrix}$$
行列 $A$ に含まれる $-1$ を $0$ 以上 $3$ 未満の整数に変えて得られる行列は $9$ 個あり、それぞれについて
$\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$
で、行列式の総和は $5+3+1+4+2+0+3+1+(-1)=18$ です。これを $3$ で割ったあまりである $0$ が答えになります。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。