No.2445 奇行列式
タグ : / 解いたユーザー数 25
作問者 : 👑
p-adic
/ テスター :
Shirotsume
注意
この問題の実行時間制限は3000[ms]です。
問題文
入力に $2$ 個の正整数 $N$ と $B$ と、非負整数係数 $N$ 次正方行列 $A$ が与えられます。
$N$ 以下の各正整数 $i, j$ に対し、$A$ の $(i,j)$ 成分を $A_{i,j}$ と置きます。
$N$ 次奇置換 $\sigma$ 全体をわたる $\prod_{i=1}^{N} A_{i,\sigma(i)}$ の総和を $B$ で割った余りを求めてください。
以下、奇置換について知らない人向けの説明をします。（クリックで開く）
正整数 $n$ に対し、$n$ 次の置換とは大雑把には $n$ 以下の正整数をシャッフルする関数のことです。より正確には以下のように定義されます：
定義（置換）
$n$ 以下の正整数全体の集合を $I_n$ と置く。$n$ 次の置換とは、 $I_n$ から $I_n$ への全単射な写像である。
$a$ を $n$ 次の置換とします。$a$ が互換であるとは、大雑把には $a$ がちょうど $2$ つの数を入れ替えるということです。より正確には、以下を満たす $n$ 以下の正整数 $i$ と $j$ が存在するということです：
- $i \neq j$ である。
- $a(i) = j$ である。
- $a(j) = i$ である。
- $n$ 以下の任意の正整数 $k$ に対し、$k \neq i$ かつ $k \neq j$ ならば、$a(k) = k$ である。
互換を用いて、偶置換と奇置換という概念を以下のように定めます：
- 偶数個の互換の合成で表せる $n$ 次の置換を、$n$ 次の偶置換と呼ぶ。
- 偶数個の互換の合成で表せない $n$ 次の置換を、$n$ 次の奇置換と呼ぶ。
ただし互換 $0$ 個の合成は恒等置換として定義されます。従って恒等置換は偶置換です。
入力
入力は次の形式で標準入力から $1 + N$ 行で与えられます：
- $1$ 行目に $N, B$ が半角空白区切りで与えられます。
- $N$ 以下の各正整数 $i$ に対し、$1 + i$ 行目に $A$ の第 $i$ 行の各成分が半角空白区切りで与えられます。
$N$ $B$
$A_{1,1}$ $\cdots$ $A_{1,N}$
$\vdots$
$A_{N,1}$ $\cdots$ $A_{N,N}$
制約
入力は以下の制約を満たします：
- $N$ は $1 \leq N \leq 20$ を満たす整数である。
- $B$ は $1 \leq B \leq 10^9$ を満たす整数である。
- $N$ 以下の任意の正整数 $i, j$ に対し、$A_{i,j}$ は $0 \leq A_{i,j} \leq 10^{18}$ を満たす整数である。
出力
$N$ 次奇置換 $\sigma$ 全体をわたる $\prod_{i=1}^{N} A_{i,\sigma(i)}$ の総和を $B$ で割った余りを求めてください。
最後に改行してください。
サンプル
サンプル1
入力
1 2 3
出力
0
$N = 1$ 次の置換は恒等置換に限られ、恒等置換は偶置換です。従って求める総和は $0$ であり、$0$ を $B = 2$ で割った余りは $0$ です。
サンプル2
入力
2 3 1 2 3 1
出力
0
$2$ 次の置換は恒等置換と互換 $(1,2)$ の $2$ つがあります。前者は偶置換であり後者は奇置換であるので、求める総和は
$\displaystyle A_{1,2} A_{2,1} = 2 \times 3 = 6 $
です。$6$ を $B = 3$ で割った余りは $0$ です。
サンプル3
入力
3 10 1 2 3 4 5 6 7 8 9
出力
5
$3$ 次の置換は $6$ つあります。そのうち奇置換は互換 $(1,2)$ と $(1,3)$ と $(2,3)$ の $3$ つあるので、求める総和は
$\displaystyle A_{1,2} A_{2,1} A_{3,3} + A_{1,3} A_{2,2} A_{3,1} + A_{1,1} A_{2,3} A_{3,2} = 2 \times 4 \times 9 + 3 \times 5 \times 7 + 1 \times 6 \times 8 = 72 + 105 + 48 = 225 $
です。$225$ を $B = 10$ で割った余りは $5$ です。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。