Product of all sorted subsets of size K using elements whose index divide K completely | Java implementation of 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
import java . util . * ; class GFG { static int p = 1000000007 ; static int power ( int x , int y , int p ) { int 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 ; } static void nCr ( int n , int p , int f [ ] [ ] , int m ) { for ( int i = 0 ; i <= n ; i ++ ) { for ( int 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 ; } } } } static void ProductOfSubsets ( int arr [ ] , int n , int m ) { int [ ] [ ] f = new int [ n + 1 ] [ 100 ] ; nCr ( n , p - 1 , f , m ) ; Arrays . sort ( arr ) ; long ans = 1 ; for ( int i = 0 ; i < n ; i ++ ) { int x = 0 ; for ( int 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 ) ; } System . out . print ( ans + "NEW_LINE"); } public static void main ( String [ ] args ) { int arr [ ] = { 4 , 5 , 7 , 9 , 3 } ; int K = 4 ; int N = arr . length ; ProductOfSubsets ( arr , N , K ) ; } }