Find sum of f ( s ) for all the chosen sets from the given array | C ++ implementation of the approach ; To store the factorial and the factorial mod inverse of a number ; Function to find ( a ^ m1 ) % mod ; Function to find factorial of all the numbers ; Function to find the factorial mod inverse of all the numbers ; Function to return nCr ; Function to find sum of f ( s ) for all the chosen sets from the given array ; Sort the given array ; Calculate the factorial and modinverse of all elements ; For all the possible sets Calculate max ( S ) and min ( S ) ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define N  100005 NEW_LINE #define mod  (int)(1e9 + 7) NEW_LINE int factorial [ N ] , modinverse [ N ] ; int power ( int a , int m1 ) { if ( m1 == 0 ) return 1 ; else if ( m1 == 1 ) return a ; else if ( m1 == 2 ) return ( 1LL * a * a ) % mod ; else if ( m1 & 1 ) return ( 1LL * a * power ( power ( a , m1 / 2 ) , 2 ) ) % mod ; else return power ( power ( a , m1 / 2 ) , 2 ) % mod ; } void factorialfun ( ) { factorial [ 0 ] = 1 ; for ( int i = 1 ; i < N ; i ++ ) factorial [ i ] = ( 1LL * factorial [ i - 1 ] * i ) % mod ; } void modinversefun ( ) { modinverse [ N - 1 ] = power ( factorial [ N - 1 ] , mod - 2 ) % mod ; for ( int i = N - 2 ; i >= 0 ; i -- ) modinverse [ i ] = ( 1LL * modinverse [ i + 1 ] * ( i + 1 ) ) % mod ; } int binomial ( int n , int r ) { if ( r > n ) return 0 ; int a = ( 1LL * factorial [ n ] * modinverse [ n - r ] ) % mod ; a = ( 1LL * a * modinverse [ r ] ) % mod ; return a ; } int max_min ( int a [ ] , int n , int k ) { sort ( a , a + n ) ; factorialfun ( ) ; modinversefun ( ) ; long long ans = 0 ; k -- ; for ( int i = 0 ; i < n ; i ++ ) { int x = n - i - 1 ; if ( x >= k ) ans -= binomial ( x , k ) * a [ i ] % mod ; int y = i ; if ( y >= k ) ans += binomial ( y , k ) * a [ i ] % mod ; ans = ( ans + mod ) % mod ; } return ( int ) ( ans ) ; } int main ( ) { int a [ ] = { 1 , 1 , 3 , 4 } , k = 2 ; int n = sizeof ( a ) / sizeof ( int ) ; cout << max_min ( a , n , k ) ; return 0 ; }