Find sum of f ( s ) for all the chosen sets from the given array | Python3 implementation of the approach ; To store the factorial and the factorial mod inverse of a number ; 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
N = 100005 NEW_LINE mod = ( 10 ** 9 + 7 ) NEW_LINE factorial = [ 0 ] * N NEW_LINE modinverse = [ 0 ] * N NEW_LINE def factorialfun ( ) : NEW_LINE INDENT factorial [ 0 ] = 1 NEW_LINE for i in range ( 1 , N ) : NEW_LINE INDENT factorial [ i ] = ( factorial [ i - 1 ] * i ) % mod NEW_LINE DEDENT DEDENT def modinversefun ( ) : NEW_LINE INDENT modinverse [ N - 1 ] = pow ( factorial [ N - 1 ] , mod - 2 , mod ) % mod NEW_LINE for i in range ( N - 2 , - 1 , - 1 ) : NEW_LINE INDENT modinverse [ i ] = ( modinverse [ i + 1 ] * ( i + 1 ) ) % mod NEW_LINE DEDENT DEDENT def binomial ( n , r ) : NEW_LINE INDENT if ( r > n ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT a = ( factorial [ n ] * modinverse [ n - r ] ) % mod NEW_LINE a = ( a * modinverse [ r ] ) % mod NEW_LINE return a NEW_LINE DEDENT def max_min ( a , n , k ) : NEW_LINE INDENT a = sorted ( a ) NEW_LINE factorialfun ( ) NEW_LINE modinversefun ( ) NEW_LINE ans = 0 NEW_LINE k -= 1 NEW_LINE for i in range ( n ) : NEW_LINE INDENT x = n - i - 1 NEW_LINE if ( x >= k ) : NEW_LINE INDENT ans -= ( binomial ( x , k ) * a [ i ] ) % mod NEW_LINE DEDENT y = i NEW_LINE if ( y >= k ) : NEW_LINE INDENT ans += ( binomial ( y , k ) * a [ i ] ) % mod NEW_LINE DEDENT ans = ( ans + mod ) % mod NEW_LINE DEDENT return ans NEW_LINE DEDENT a = [ 1 , 1 , 3 , 4 ] NEW_LINE k = 2 NEW_LINE n = len ( a ) NEW_LINE print ( max_min ( a , n , k ) ) NEW_LINE