codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1670C.md (3544B)


      1 Source: https://codeforces.com/problemset/problem/1670/C
      2 
      3 C. Where is the Pizza?
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 While searching for the pizza, baby Hosssam came across two permutations $a$ and $b$ of length $n$.
     22 
     23 Recall that a permutation is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array) and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).
     24 
     25 Baby Hosssam forgot about the pizza and started playing around with the two permutations. While he was playing with them, some elements of the first permutation got mixed up with some elements of the second permutation, and to his surprise those elements also formed a permutation of size $n$.
     26 
     27 Specifically, he mixed up the permutations to form a new array $c$ in the following way.
     28 
     29 * For each $i$ ($1\le i\le n$), he either made $c_i=a_i$ or $c_i=b_i$.
     30 * The array $c$ is a permutation.
     31 
     32 You know permutations $a$, $b$, and values at some positions in $c$. Please count the number different permutations $c$ that are consistent with the described process and the given values. Since the answer can be large, print it modulo $10^9+7$.
     33 
     34 It is guaranteed that there exists at least one permutation $c$ that satisfies all the requirements.
     35 
     36 Input
     37 
     38 The first line contains an integer $t$ ($1 \le t \le 10^5$) — the number of test cases.
     39 
     40 The first line of each test case contains a single integer $n$ ($1\le n\le 10^5$) — the length of the permutations.
     41 
     42 The next line contains $n$ distinct integers $a_1,a_2,\ldots,a_n$ ($1\le a_i\le n$) — the first permutation.
     43 
     44 The next line contains $n$ distinct integers $b_1,b_2,\ldots,b_n$ ($1\le b_i\le n$) — the second permutation.
     45 
     46 The next line contains $n$ distinct integers $d_1,d_2,\ldots,d_n$ ($d_i$ is either $0$, $a_i$, or $b_i$) — the description of the known values of $c$. If $d_i=0$, then there are no requirements on the value of $c_i$. Otherwise, it is required that $c_i=d_i$.
     47 
     48 It is guaranteed that there exists at least one permutation $c$ that satisfies all the requirements.
     49 
     50 It is guaranteed that the sum of $n$ over all test cases does not exceed $5 \cdot 10^5$.
     51 
     52 Output
     53 
     54 For each test case, print the number of possible permutations $c$, modulo $10^9+7$.
     55 
     56 Example
     57 
     58 Input
     59 
     60 ```
     61 9
     62 
     63 7
     64 
     65 1 2 3 4 5 6 7
     66 
     67 2 3 1 7 6 5 4
     68 
     69 2 0 1 0 0 0 0
     70 
     71 1
     72 
     73 1
     74 
     75 1
     76 
     77 0
     78 
     79 6
     80 
     81 1 5 2 4 6 3
     82 
     83 6 5 3 1 4 2
     84 
     85 6 0 0 0 0 0
     86 
     87 8
     88 
     89 1 6 4 7 2 3 8 5
     90 
     91 3 2 8 1 4 5 6 7
     92 
     93 1 0 0 7 0 3 0 5
     94 
     95 10
     96 
     97 1 8 6 2 4 7 9 3 10 5
     98 
     99 1 9 2 3 4 10 8 6 7 5
    100 
    101 1 9 2 3 4 10 8 6 7 5
    102 
    103 7
    104 
    105 1 2 3 4 5 6 7
    106 
    107 2 3 1 7 6 5 4
    108 
    109 0 0 0 0 0 0 0
    110 
    111 5
    112 
    113 1 2 3 4 5
    114 
    115 1 2 3 4 5
    116 
    117 0 0 0 0 0
    118 
    119 5
    120 
    121 1 2 3 4 5
    122 
    123 1 2 3 5 4
    124 
    125 0 0 0 0 0
    126 
    127 3
    128 
    129 1 2 3
    130 
    131 3 1 2
    132 
    133 0 0 0
    134 ```
    135 
    136 Output
    137 
    138 ```
    139 4
    140 1
    141 2
    142 2
    143 1
    144 8
    145 1
    146 2
    147 2
    148 ```
    149 
    150 Note
    151 
    152 In the first test case, there are $4$ distinct permutation that can be made using the process: $[2,3,1,4,5,6,7]$, $[2,3,1,7,6,5,4]$, $[2,3,1,4,6,5,7]$, $[2,3,1,7,5,6,4]$.
    153 
    154 In the second test case, there is only one distinct permutation that can be made using the process: $[1]$.
    155 
    156 In the third test case, there are $2$ distinct permutation that can be made using the process: $[6,5,2,1,4,3]$, $[6,5,3,1,4,2]$.
    157 
    158 In the fourth test case, there are $2$ distinct permutation that can be made using the process: $[1,2,8,7,4,3,6,5]$, $[1,6,4,7,2,3,8,5]$.
    159 
    160 In the fifth test case, there is only one distinct permutation that can be made using the process: $[1,9,2,3,4,10,8,6,7,5]$.