問題一覧 > 教育的問題

No.2445 Odd Determinant

レベル : / AI推定難易度 : 1650 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 27
作問者 : 👑 p-adic / テスター : Shirotsume
お気に入りにしたユーザー ProblemId : 9397 / 自分の提出
問題文最終更新日: 2023-07-30 13:10:44
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 402 (順位表) の他の問題:

Note

The time limit for this problem is 3000[ms].

Problem Statement

You are given as input $2$ positive integers $N$ and $B$, and a square matrix $A$ of order $N$ with non-negative integer coefficients.

 

For each pair of positive integers $i, j$ not greater than $N$, let $A_{i,j}$ denote the $(i,j)$ entry of $A$.

Find the sum of $\prod_{i=1}^{N} A_{i,\sigma(i)}$ over all odd permutations $\sigma$ of order $N$, modulo $B$.

 

Below is an explanation for those unfamiliar with odd permutations. (Click to open)

 

For a positive integer $n$, a permutation of order $n$ is, roughly speaking, a function that shuffles the positive integers not greater than $n$. More precisely, it is defined as follows:

 

Definition (Permutation)

Let $I_n$ be the set of all positive integers not greater than $n$. A permutation of order $n$ is a bijective map from $I_n$ to $I_n$.

 

Let $a$ be a permutation of order $n$. Saying that $a$ is a transposition means, roughly speaking, that $a$ swaps exactly $2$ numbers. More precisely, it means that there exist positive integers $i$ and $j$ not greater than $n$ satisfying the following:

  1. $i \neq j$.
  2. $a(i) = j$.
  3. $a(j) = i$.
  4. For every positive integer $k$ not greater than $n$, if $k \neq i$ and $k \neq j$, then $a(k) = k$.

Using transpositions, the notions of even and odd permutations are defined as follows:

  1. A permutation of order $n$ that can be expressed as a composition of an even number of transpositions is called an even permutation of order $n$.
  2. A permutation of order $n$ that cannot be expressed as a composition of an even number of transpositions is called an odd permutation of order $n$.

Here, the composition of $0$ transpositions is defined to be the identity permutation. Therefore, the identity permutation is an even permutation.

Input

The input is given from standard input in $1 + N$ lines in the following format:

  • The $1$st line contains $N, B$, separated by a single-byte space.
  • For each positive integer $i$ not greater than $N$, line $1 + i$ contains the entries of the $i$-th row of $A$, separated by single-byte spaces.
$N$ $B$
$A_{1,1}$ $\cdots$ $A_{1,N}$
$\vdots$
$A_{N,1}$ $\cdots$ $A_{N,N}$

Constraints

The input satisfies the following constraints:

  • $N$ is an integer satisfying $1 \leq N \leq 20$.
  • $B$ is an integer satisfying $1 \leq B \leq 10^9$.
  • For all positive integers $i, j$ not greater than $N$, $A_{i,j}$ is an integer satisfying $0 \leq A_{i,j} \leq 10^{18}$.

Output

Output the remainder when the sum of $\prod_{i=1}^{N} A_{i,\sigma(i)}$ over all odd permutations $\sigma$ of order $N$ is divided by $B$.

Print a newline at the end.

Sample

Sample 1
Input
1 2
3
Output
0

The only permutation of order $N = 1$ is the identity permutation, which is an even permutation. Therefore, the desired sum is $0$, and the remainder when $0$ is divided by $B = 2$ is $0$.

Sample 2
Input
2 3
1 2
3 1
Output
0

There are $2$ permutations of order $2$: the identity permutation and the transposition $(1,2)$. The former is an even permutation and the latter is an odd permutation, so the desired sum is

$\displaystyle A_{1,2} A_{2,1} = 2 \times 3 = 6 $

. The remainder when $6$ is divided by $B = 3$ is $0$.

Sample 3
Input
3 10
1 2 3
4 5 6
7 8 9
Output
5

There are $6$ permutations of order $3$. Among them, the odd permutations are the $3$ transpositions $(1,2)$, $(1,3)$, and $(2,3)$, so the desired sum is

$\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 $

. The remainder when $225$ is divided by $B = 10$ is $5$.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。