No.2445 Odd Determinant
タグ : / 解いたユーザー数 27
作問者 : 👑
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:
- $i \neq j$.
- $a(i) = j$.
- $a(j) = i$.
- 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:
- 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$.
- 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もしくは右上の雲マークをクリックしてアカウントを作成してください。