Product of all Subsequences of size K except the minimum and maximum Elements | C ++ program to find product of all Subsequences of size K except the minimum and maximum Elements ; 2D array to store value of combinations nCr ; Function to pre - calculate value of all combinations nCr ; Function to calculate product of all subsequences except the minimum and maximum elements ; Sorting array so that it becomes easy to calculate the number of times an element will come in first or last place ; An element will occur ' powa ' times in total of which ' powla ' times it will be last element and ' powfa ' times it will be first element ; In total it will come powe = powa - powla - powfa times ; Multiplying a [ i ] powe times using Fermat Little Theorem under MODulo MOD for fast exponentiation ; Driver Code ; pre - calculation of all combinations
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define MOD  1000000007 NEW_LINE #define ll  long long NEW_LINE #define max  101 NEW_LINE ll C [ max - 1 ] [ max - 1 ] ; ll power ( ll x , unsigned ll y ) { unsigned ll res = 1 ; x = x % MOD ; while ( y > 0 ) { if ( y & 1 ) { res = ( res * x ) % MOD ; } y = y >> 1 ; x = ( x * x ) % MOD ; } return res % MOD ; } void combi ( int n , int k ) { int i , j ; for ( i = 0 ; i <= n ; i ++ ) { for ( j = 0 ; j <= min ( i , k ) ; j ++ ) { if ( j == 0 j == i ) C [ i ] [ j ] = 1 ; else C [ i ] [ j ] = ( C [ i - 1 ] [ j - 1 ] % MOD + C [ i - 1 ] [ j ] % MOD ) % MOD ; } } } unsigned ll product ( ll a [ ] , int n , int k ) { unsigned ll ans = 1 ; sort ( a , a + n ) ; ll powa = C [ n - 1 ] [ k - 1 ] ; for ( int i = 0 ; i < n ; i ++ ) { ll powla = C [ i ] [ k - 1 ] ; ll powfa = C [ n - i - 1 ] [ k - 1 ] ; ll powe = ( ( powa % MOD ) - ( powla + powfa ) % MOD + MOD ) % MOD ; unsigned ll mul = power ( a [ i ] , powe ) % MOD ; ans = ( ( ans % MOD ) * ( mul % MOD ) ) % MOD ; } return ans % MOD ; } int main ( ) { combi ( 100 , 100 ) ; ll arr [ ] = { 1 , 2 , 3 , 4 } ; int n = sizeof ( arr ) / sizeof arr [ 0 ] ; int k = 3 ; unsigned ll ans = product ( arr , n , k ) ; cout << ans << endl ; return 0 ; }