[Solution] Good Permutations Solution Codechef
You are given two arrays � and �, each of size �.
Let � denote a permutation length �. The permutation � is said to be good, if you can make an array � where:
- ��=��+��� or ��=��−���, for all (1≤�≤�);
- All elements of � are equal.
Out of the �! possible permutations, find the count of good permutations.
Since the count can be huge, output it modulo 109+7.
Note that a permutation of length � consists of all integers from 1 to � exactly once.
Input Format
- 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 consists of a single integer � – the size of arrays.
- The second line of each test case consists of � space-separated integers �1,�2,…,��, the elements of array A.
- The third line of each test case consists of N space-separated integers �1,�2,…,��, the elements of array B.
Output Format Good Permutations Solution Codechef
For each test case, output on a new line, the count of good permutations, modulo 109+7.
Constraints Good Permutations Solution Codechef
- 1≤�≤105
- 1≤�≤105
- −109≤��≤109
- −109≤��≤109
- The sum of � over all test cases won’t exceed 2⋅105.
Sample 1: Good Permutations Solution Codechef
4 3 10 5 2 -7 -4 -1 3 6 7 8 -6 5 7 6 2 6 5 5 5 4 7 -5 4 -4 -4 -3 4 2 2 2 2 3 3 -3 -3
1 2 6 24
Explanation: Good Permutations Solution Codechef
Test case 1: The only good permutation is [3,2,1]. We construct � as following:
- �1=�1+��1=�1+�3=10−1=9;
- �2=�2−��2=�2−�2=5−(−4)=9;
- �3=�3−��3=�3−�1=2−(−7)=9.
Here all elements of array � are equal. It can be shown that for all other permutations, it is impossible to create such an array �. Thus, the count of good permutations is 1.
Test case 2: The good permutations are [2,1,3],[3,2,1]. We construct � as following using [2,1,3]:
- �1=�1−��1=�1−�2=6−5=1;
- �2=�2+��2=�2+�1=7+(−6)=1;
- �3=�3−��3=�3−�3=8−7=1.
Here all elements of array � are equal. It can be shown that for [3,2,1], it is possible to create such an array �. Thus, the count of good permutations is 2.