[Solution] Count Arrays solution codechef

Count Arrays solution codechef – Given an array AA of length NN such that 1AiN1≤Ai≤N and Aii,Ai≠i, i[1,N]∀i∈[1,N].

Count the number of arrays BB of length NN such that i[1,N]∀i∈[1,N]:

  • BiBAiBi≠BAi
  • 1BiM1≤Bi≤M

Since the answer may be large, print it modulo 109+7109+7.

Count Arrays solution codechef

  • The first line contains a single integer TT − the number of test cases. The description of TT test cases follows.
  • Each test case contains 22 lines of input:
    • The first line of each test case contains two space separated integers NNMM.
    • The second line of each test case contains NN space separated integers A1,A2,,ANA1,A2,…,AN.

Output Format

For each test case, output a single integer on a newline – answer modulo 109+7109+7.


  • 1T1051≤T≤105
  • 2N1052≤N≤105
  • 1M1001≤M≤100
  • 1AiN,Aii1≤Ai≤N,Ai≠i
  • Sum of NN over all test cases does not exceed 106106

Count Arrays solution codechef


2 3
2 1
3 2
2 1 1

Sample Output 1 


Explanation Count Arrays solution codechef

Test Case 11: There are 66 possible arrays – [1,2],[2,1],[1,3],[3,1],[2,3],[3,2][1,2],[2,1],[1,3],[3,1],[2,3],[3,2].

Test Case 22: There are 22 possible arrays – [1,2,2],[2,1,1][1,2,2],[2,1,1].

Leave a Comment