Product of all sorted subsets of size K using elements whose index divide K completely | Javascript implementation for the above approach ; Iterative Function to calculate ( x ^ y ) % p in O ( log y ) ; If y is odd , multiply x with result ; y must be even now ; Iterative Function to calculate ( nCr ) % p and save in f [ n ] [ r ] ; If j > i then C ( i , j ) = 0 ; If iis equal to j then C ( i , j ) = 1 ; Function calculate the Final answer ; Initialize ans ; x is count of occurence of arr [ i ] in different set such that index of arr [ i ] in those sets divides K completely . ; Finding the count of arr [ i ] by placing it at index which divides K completely ; By Fermat 's theorem ; Driver Code
let p = 1000000007 ; function power ( x , y , p ) { let res = 1 ; x = x % p ; while ( y > 0 ) { if ( y % 2 == 1 ) res = ( res * x ) % p ; y = y >> 1 ; x = ( x * x ) % p ; } return res ; } function nCr ( n , p , f , m ) { for ( let i = 0 ; i <= n ; i ++ ) { for ( let j = 0 ; j <= m ; j ++ ) { if ( j > i ) { f [ i ] [ j ] = 0 ; } else if ( j == 0 j == i ) { f [ i ] [ j ] = 1 ; } else { f [ i ] [ j ] = ( f [ i - 1 ] [ j ] + f [ i - 1 ] [ j - 1 ] ) % p ; } } } } function ProductOfSubsets ( arr , n , m ) { let f = new Array ( n + 1 ) ; for ( var i = 0 ; i < f . length ; i ++ ) { f [ i ] = new Array ( 2 ) ; } nCr ( n , p - 1 , f , m ) ; arr . sort ( ) ; let ans = 1 ; for ( let i = 0 ; i < n ; i ++ ) { let x = 0 ; for ( let j = 1 ; j <= m ; j ++ ) { if ( m % j == 0 ) { x = ( x + ( f [ n - i - 1 ] [ m - j ] * f [ i ] [ j - 1 ] ) % ( p - 1 ) ) % ( p - 1 ) ; } } ans = ( ( ans * power ( arr [ i ] , x , p ) ) % p ) ; } document . write ( ans + " " ) ; } let arr = [ 4 , 5 , 7 , 9 , 3 ] ; let K = 4 ; let N = arr . length ; ProductOfSubsets ( arr , N , K ) ;