G. Permutant

Codeforces

IDCF10212G

Time3000ms

Memory512MB

Difficulty—

English · Original

Formal · Original

Consider an $n times n$ matrix $A$. Let us denote element in $i$-th row and $j$-th column as $A^((i))_j$. You are given a sequence $a_1, \\dots, a_n$ and a permutation $pi_1, \\dots, pi_n$ such that the first row is formed by sequence $a_k$: $$A^{(1)}_k = a_k$$ And any consequent row is formed by applying permutation $pi_k$ to the previous one: $$A^{(i)}_k = A^{(i-1)}_{\pi_k}$$ Your task is to calculate $det A$: the determinant of matrix $A$. Since it may be very large, output it modulo $10^9 + 7$. The first line of input contains a single integer $n$ ($1 <= n <= 5000$). The second line of input contains $n$ integers $a_1, \\dots, a_n$ ($1 <= a_i <= 10^9$). The third line of input contains $n$ distinct integers $pi_1, \\dots, pi_n$ ($1 <= pi_i <= n$). Output a single number which is the answer to the problem. Recall that the determinant can be defined as follows: $$\det A = \sum\limits_{\sigma \in S_n} \mathrm{sgn} (\sigma) \prod\limits_{i = 1}^{n} A^{(i)}_{\sigma_i}$$ Here, $S_n$ is the set of all permutations of ${1, \\dots, n}$, and $upright(s g n) (sigma)$ is the sign of permutation $sigma$: $-1$ if it has an odd number of inversions and $+ 1$ if this number is even. An inversion is a pair of indices $(i, j)$ such that $i < j$ but $sigma_i > sigma_j$. ## Input The first line of input contains a single integer $n$ ($1 <= n <= 5000$).The second line of input contains $n$ integers $a_1, \\dots, a_n$ ($1 <= a_i <= 10^9$).The third line of input contains $n$ distinct integers $pi_1, \\dots, pi_n$ ($1 <= pi_i <= n$). ## Output Output a single number which is the answer to the problem. [samples] ## Note Recall that the determinant can be defined as follows:$$\det A = \sum\limits_{\sigma \in S_n} \mathrm{sgn} (\sigma) \prod\limits_{i = 1}^{n} A^{(i)}_{\sigma_i}$$Here, $S_n$ is the set of all permutations of ${1, \\dots, n}$, and $upright(s g n) (sigma)$ is the sign of permutation $sigma$: $-1$ if it has an odd number of inversions and $+ 1$ if this number is even. An inversion is a pair of indices $(i, j)$ such that $i < j$ but $sigma_i > sigma_j$.

**Definitions** Let $ n \in \mathbb{Z}^+ $, $ \mathbf{a} = (a_1, \dots, a_n) \in \mathbb{Z}^n $, and $ \pi = (\pi_1, \dots, \pi_n) \in S_n $ be a permutation. Define the $ n \times n $ matrix $ A $ such that: - $ A^{(1)}_j = a_j $ for $ j = 1, \dots, n $, - $ A^{(i)}_j = A^{(i-1)}_{\pi_j} $ for $ i = 2, \dots, n $ and $ j = 1, \dots, n $. **Constraints** 1. $ 1 \leq n \leq 5000 $ 2. $ 1 \leq a_i \leq 10^9 $ for all $ i $ 3. $ \pi \in S_n $, i.e., $ \pi $ is a permutation of $ \{1, \dots, n\} $ **Objective** Compute $ \det A \mod (10^9 + 7) $, where: $$ \det A = \sum_{\sigma \in S_n} \mathrm{sgn}(\sigma) \prod_{i=1}^n A^{(i)}_{\sigma_i} $$

API Response (JSON)

{
  "problem": {
    "name": "G. Permutant",
    "description": {
      "content": "Consider an $n times n$ matrix $A$. Let us denote element in $i$-th row and $j$-th column as $A^((i))_j$. You are given a sequence $a_1, \\\\dots, a_n$ and a permutation $pi_1, \\\\dots, pi_n$ such that ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10212G"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Consider an $n times n$ matrix $A$. Let us denote element in $i$-th row and $j$-th column as $A^((i))_j$.\n\nYou are given a sequence $a_1, \\\\dots, a_n$ and a permutation $pi_1, \\\\dots, pi_n$ such that ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $, $ \\mathbf{a} = (a_1, \\dots, a_n) \\in \\mathbb{Z}^n $, and $ \\pi = (\\pi_1, \\dots, \\pi_n) \\in S_n $ be a permutation.  \nDefine the $ n \\times n $ matrix $ A ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments