Beautiful Array

Since we have to use elements from [1, N] and make the longest increasing subsequence, we must use all elements of [1, N] and for ‘N’ position out of ‘M’, place them in increasing order.

Like for ‘N’ = 3, ‘M’ = 5, some possible placements of ‘N’ elements are

Array[ ]   :   _ 1  _  2  3

position :  1  2  3  4  5

Array[ ]   :   _ 1  2  _  3

position :  1  2  3  4  5

So, we have ( M C N) ways to select the ‘N’ position such that the selected position makes an increasing subsequence of length ‘N’. For example (N = 3 and M = 5 ) we have 10 ways (5 C 3) to select 3 positions out of 5, such that the selected position makes an increasing subsequence of length 3. Let the selected position be {p1, p2, p3 ...pn}.

After doing so our task is to fill the gaps.

Now to avoid repetition of the array, we don’t place 1 before p1, don’t place 2 before p2 and after p1, don’t place 3 before p3 and after p2, and so on.

We can say in the set {p1, p2, p3 ...pn} p1, p2, p3….pn are the first positions of 1, 2, 3..N respectively.

If we carefully observe, there are (‘N’ - 1) ways to fill not filled positions before ‘pn’ (the first position of N) and ‘N’ ways to fill each not filled position after ‘pn’.

Let x = ‘pn’  -  N, be the not filled position to the left of ‘pn’ and y = M - ‘pn’,  be the not filled position to the right of ‘pn’.

So, loop for each ‘pn’ position from N to M, and find the number of ways for each position of ‘pn’ and add to our answer.

Total number of ways for each pn  = ( (pn - 1) C (N -1) )( pow (x, N-1) ) * ( pow(y, N) )), where n C r denotes the total combination of ‘r’ elements among ‘n’.

We have done (('pn' - 1) C (N - 1)) not (pn C N) because we have to fix ‘N’-th element at ‘pn’ and arrange only ‘N’ - 1 element in ‘pn’ -1 positions such that it maintains the constraints of the question( increasing subsequence).

Note:

• Take care of modulo operation where mod = 10^9 +7.
• Since this question has a different number of queries, So pre-calculate factorial, and multiplicative modular inverse.

Algorithm :

• Take ‘factorial’ and ‘inverse’ array that stores the factorial and modular multiplicative inverse.
• Do precalculation by calling the function ‘preCalculate( factorial, inverse)’.
• Take the vector ‘res’, which stores the answer of each query.
• Do the following for each query from 0 to ‘N’.
  • Let ‘n’ = arr[i][0] and ‘m’ = arr[i][1],  be pairs of numbers given.
  • Let ‘ans’ be the variable to store the answer ( number of the beautiful arrays)
  • Let ‘n1powx’ be variable initialized to 1.
  • Let ‘npowx’ be the variable initialized to power( ‘n’, ‘m’ -’n’)
  • Let ‘inverseN’ be the modular multiplicative inverse  of ‘n’ under mod.
  • Take a counter ‘i’ and run a loop from ‘n’ to ‘m’
    • Calculate iCm by calling the function nCk(i-1, n-1) and store it in variable nck.
    • Update ‘ans’ i.e ans = ( ( (nck * npowx) % mod ) * n1powx ) % mod
    • Update ‘n1powx’ as n1powx = ( n1powx * (n -1)) % mod
    • Update ‘npowx’ as npowx = (npowx * inverseN) % mod
  • Push (ans%mod) in  ‘res’ vector
• return ‘res’

Description of preCalculate ( factorial, inverse ) function:

• Initialize, factorial[0] = 1
• Initialize, inverse[0] = inverse[1] = 1
• Run a loop from 1 to 5 * 10 ^ 3.
  • Store factorial[i] = (factorial [i - 1] * i) % 'mod'
  • Store inverse[i] = multiverse( factorial [i], mod.

Description of modInverse (num, mod) function:

    This function returns the modular multiplicative inverse of num under modulo ‘mod’ 

• Let ‘x’ and ‘y’ be the variable that satisfies the extended euclidean equation on ‘num’ and ‘mod’
• Just find the value of ‘x’ and ‘y’ using an extended Euclidean algorithm.
• If ’x’ if negative then add ‘mod’ to it as ‘x’ = ‘x’ + ‘mod’
• Return ‘x’
   

Description of nCk( ‘n’, ‘k’) function:

• Return (((factorial [ n ] * inverse [k] ) % mod ) * inverse[n-k] ) % mod)

O( M * Q)   where ‘M’ is the length of the beautiful array and Q is the number of queries.

For each query, we are calculating the number of ways for each placement of the ‘N-th' element from ‘N’ to ‘M’ that takes O(M) time. And also we are precalculating the factorial that takes O(M) time. Hence time complexity is O(M * Q).

O(‘M’)  where ‘M’ is the maximum range of array length.

We are pre-Calculating and storing the factorial and modular multiplicative inverse that takes O(M) space.