# Beautiful Array

Posted: 18 Jun, 2021
Difficulty: Hard

## PROBLEM STATEMENT

#### The array of length ‘M’ is said to be beautiful if -

``````The array consists of elements from 1 to ‘N’.

The array contains at least one ‘N’ length strictly increasing subsequence.
``````

#### Note:

``````A subsequence of an array is an ordered subset of the array's elements having the same sequential ordering as the original array. For example, the subsequences of the array  [1, 2, 3] are , , , [1, 2], [1, 3], [2, 3] and [1, 2, 3] where  [2, 1], [3,2, 1] are not subsequence of array [1, 2, 3]

The longest increasing subsequence of an array of numbers is the longest possible subsequence that can be created from its elements such that all elements are in strictly increasing order.
``````

#### For example:

``````For M = 3 and N = 2
array : [ 1, 1, 2 ] [ 1, 2, 1 ] [ 1, 2, 2 ] [ 2, 1, 2 ] are beautiful.

array:  [ 1, 1, 1 ] [ 2, 1, 1 ] [ 2, 2, 1 ] [ 2, 2, 2 ] are not beautiful.
``````
##### Input Format:
``````The first line of input contains an integer ‘Q’, denoting the number of queries. Then each query follows.

The first line and the only of each query contains a pair of integers ‘M’ and ‘N’ , where ‘M’ is the length of the array and ‘N’ is the range of elements.
``````
##### Output Format:
``````For each query, print a single line containing ‘X’, denoting the number of beautiful arrays of length ‘M’.

As this number can be quite large, print your answer modulo 10 ^ 9 + 7.

The output of each test case will be printed on a separate line.
``````
##### Note:
``````You do not need to print anything, it has already been taken care of. Just implement the given function.
``````
##### Constraints:
``````1 <= Q <= 500
1 <= N <= M <= 5 * 10 ^ 3

Time Limit: 1 sec.
`````` Approach 1

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] and ‘m’ = arr[i],  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 = 1
• Initialize, inverse = inverse = 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)