Find product of all elements at indexes which are factors of M for all possible sorted subsequences of length M | C ++ program to find the product of all the combinations of M elements from an array whose index in the sorted order divides M completely ; 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 ] C ( n , r ) % p = [ C ( n - 1 , r - 1 ) % p + C ( n - 1 , r ) % p ] % p and C ( n , 0 ) = C ( n , n ) = 1 ; If j > i then C ( i , j ) = 0 ; If i is equal to j then C ( i , j ) = 1 ; C ( i , j ) = ( C ( i - 1 , j ) + C ( i - 1 , j - 1 ) ) % p ; Initialize the answer ; For every element arr [ i ] , x is count of occurrence of arr [ i ] in different set such that index of arr [ i ] in those sets divides m completely . ; Finding the count of arr [ i ] by placing it at the index which divides m completely ; Using fermat 's little theorem ; Multiplying with the count ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; typedef long long int lli ; const int m = 4 ; long long int power ( lli x , lli y , lli p ) { lli res = 1 ; x = x % p ; while ( y > 0 ) { if ( y & 1 ) res = ( res * x ) % p ; y = y >> 1 ; x = ( x * x ) % p ; } return res ; } void nCr ( lli n , lli p , lli f [ ] [ m + 1 ] ) { for ( lli i = 0 ; i <= n ; i ++ ) { for ( lli 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 ; } } } void operations ( lli arr [ ] , lli n , lli f [ ] [ m + 1 ] ) { lli p = 1000000007 ; nCr ( n , p - 1 , f ) ; sort ( arr , arr + n ) ; lli ans = 1 ; for ( lli i = 0 ; i < n ; i ++ ) { long long int x = 0 ; for ( lli 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 ) ; } cout << ans << endl ; } int main ( ) { lli arr [ ] = { 4 , 5 , 7 , 9 , 3 } ; lli n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; lli f [ n + 1 ] [ m + 1 ] ; operations ( arr , n , f ) ; }