Last Updated: 25 Nov, 2021

Subsequence Product

Hard

Asked in companies

Solve now

Problem statement

Ninja recently studied about subsequences and his teacher gave him the following challenge which no other student was able to solve till now.

You are given an array ‘A’ of size ‘N’ and an integer ‘K’. You find all the subsequences of size ‘K’ from the array ‘A’. Now for each of the subsequences, you calculate the product of all elements except the minimum element and the maximum element of the subsequence. After that you need to calculate the product of all these values.

Output the final product calculated by Ninja. Since the answer can be large, output it modulo 10^9+7.

Example :

N = 4 , K = 3
A = [ 1, 2, 3, 4 ]


Explanation : 

All subsequence of size ‘3’ are : 
[ 1, 2, 3 ]  : The product is 2.
[ 1, 2, 4 ]  : The product is 2.
[ 1, 3, 4 ]  : The product is 3.
[ 2, 3, 4 ]  : The product is 3.

The final product is 2*2*3*3 = 36.

Input Format :

The first line contains an integer 'T' which denotes the number of test cases to be run. Then the test cases follow.

The first line of each test case contains integers ‘N’ and ‘K’.

The next line contains ‘N’ integers representing the elements of array ‘A’.

Output format :

For each test case, output an integer denoting the required product modulo 10^9+7.

Print the output of each test case in a new line.

Note :

You don’t need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
3 <= N <= 5000
3 <= K <= N
1 <= A[i] <= 10^5

Time Limit : 1 sec

Solve now

Approaches

01 Approach

Approach :

Since we are interested in subsequences, the order of elements doesn’t matter.
So, we first sort the array ‘A’.
Now, we observe that some element ‘A[i]’ will occur in ‘^N-1C_K-1’ subsequences.
- This is because we have fixed the current element at index ‘i’ and we can choose ‘K-1’ more elements from the ‘N-1’ left elements.
Now, in some subsequences, this element can be a maximum element and in some it can be a minimum element. So, we need to subtract both these cases.
This element will be a maximum only if all other elements are chosen before index ‘i’.
So, there are ‘^i-1C_K-1’ such subsequences.
This element will be a minimum only if all other elements are chosen after index ‘i’.
So, there are ‘^N-iC_K-1’ such subsequences.
So, the total number of times an element at index ‘i’ will be contributing to the final answer is : ‘T’ = ‘^N-1C_K-1- ^i-1C_K-1 - ^N-iC_K-1’.
So, we need to calculate ‘A[i]’ raised to ‘T’.
We will use Fermat’s Theorem for calculating this.
a^(p-1) = 1 mod p.
So, we can say that a^T = a^(T % (p-1) ) mod p.
So, first we need to calculate the value of ‘T%(p-1)’.
But since ‘p-1’ is not prime, we will calculate ‘^NC_r’ using recurrent formula :
^NC _r = ( ^N-1 C _r ) + ( ^N-1 C _r-1 ).
After calculating x = T%(p-1) , we calculate ‘(A[i]^x) mod p’ for each ‘A[i]’.
We multiply this value with our final answer.

Algorithm :

Initialise a variable ‘ans’ = 1.
Initialise a constant ‘M’ = 10^9 + 7.
Calculate the value of ‘NCr’ for all ‘N<=5000’ and ‘r<=N’ and store in ‘C[i][j]’.
Sort the array ‘A’.
Run a loop from ‘i=0’ to ‘i=N-1’.
- Calculate ‘tot’ = ‘C[N-1][K-1]’.
- Calculate ‘maxi’ = ‘C[i][K-1]’.
- Calculate ‘mini’ = ‘C[N-i-1][K-1]’.
- Calculate ‘contr’ = ‘tot - maxi - mini’ % (M-1).
- Calculate ‘ans’ = ‘ans * power ( A[i], contr )’ % M using extended Euclid Algorithm.
Return ‘ans’ as the final result.

Solve now