[Solution] Make Them Alike Solution Codechef
You are given a permutation � of length �, an array � of size �, and an integer �.
Initially, 0≤��≤�. Consider an array �′ obtained from � by replacing all zeros in � with positive integers less than equal to �.
The array �′ will then be transformed as follows, in � steps:
- In the ��ℎ step, we set ��′=���′.
The initial array �′ is said to be beautiful, if, after the transformation of � steps, all elements of array �′ are equal.
Find the number of such beautiful arrays �′ which can be formed by changing the zeros in array � to any value ≤�. Since this number can be huge, print this number modulo 109+7.
Note that a permutation of length � contains of all elements from 1 to � exactly once.
Input Format Make Them Alike Solution Codechef
- The first line of input will contain a single integer �, denoting the number of test cases.
- Each test case consists of multiple lines of input.
- The first line of each test case contains two space-separated integers � and �, the size of the array and the maximum value it can have.
- The second line of each test case consists of � space-separated integers �1,�2,…,��, the permutation �.
- The third line of each test case consists of � space-separated integers �1,�2,…,��, the initial array �.
Output Format Make Them Alike Solution Codechef
For each test case, output on a new line, the number of such beautiful arrays �′ which can be formed by changing the zeros in array � to any value ≤�.
Constraints Make Them Alike Solution Codechef
- 1≤�≤105
- 1≤�≤2⋅105
- 1≤�≤109
- 0≤��≤�
- The sum of � over all test cases won’t exceed 2⋅105.
Sample 1: Make Them Alike Solution Codechef
3 4 3 2 1 4 3 0 2 0 2 3 2 3 1 2 0 0 0 8 54 8 1 2 4 3 6 7 5 0 0 0 0 0 0 0 0
9 8 459165024
Explanation: Make Them Alike Solution Codechef
Test case 1: The given permutation is [2,1,4,3]. One of the possible beautiful arrays is: �′=[1,2,3,2]. This is obtained by replacing the first 0 with 1 and the second 0 with 3 in the array �.
For the transformation:
- In the first step, �1′ is replaced with ��1′=�2′, that is 2. The array becomes [2,2,3,2].
- In the second step, �2′ is replaced with ��2′=�1′, that is 2. The array becomes [2,2,3,2].
- In the third step, �3′ is replaced with ��3′=�4′, that is 2. The array becomes [2,2,2,2].
- In the fourth step, �4′ is replaced with ��4′=�3′, that is 2. The array becomes [2,2,2,2].
Thus, after the transformation, all elements of the array are equal. The other beautiful arrays for this test case are: [1,2,1,2],[1,2,2,2],[2,2,1,2],[2,2,2,2],[2,2,3,3],[3,2,1,2],[3,2,2,2],[3,2,3,2].
There are 9 beautiful arrays in total.