Sum of absolute difference of all pairs raised to power K | C ++ program for the above approach ; Since K can be 100 max ; Constructor ; Initializing with - 1 ; Making vector A as 1 - Indexing ; To Calculate the value nCk ; Since nCj = ( n - 1 ) Cj + ( n - 1 ) C ( j - 1 ) ; ; Function that summation of absolute differences of all pairs raised to the power k ; Sort the given array ; Precomputation part , O ( n * k ) ; Traverse the array arr [ ] ; For each K ; Return the final answer ; Driver Code ; Given N and K ; Given array ; Creation of Object of class ; Function Call
#include <bits/stdc++.h> NEW_LINE #define ll  long long NEW_LINE using namespace std ; class Solution { public : ll ncr [ 101 ] [ 101 ] ; int n , k ; vector < ll > A ; Solution ( int N , int K , vector < ll > B ) { memset ( ncr , -1 , sizeof ( ncr ) ) ; n = N ; k = K ; A = B ; A . insert ( A . begin ( ) , 0 ) ; } ll f ( int N , int K ) ; ll pairsPower ( ) ; } ; ll Solution :: f ( int n , int k ) { if ( k == 0 ) return 1LL ; if ( n == k ) return 1LL ; if ( n < k ) return 0 ; if ( ncr [ n ] [ k ] != -1 ) return ncr [ n ] [ k ] ; return ncr [ n ] [ k ] = f ( n - 1 , k ) + f ( n - 1 , k - 1 ) ; } ll Solution :: pairsPower ( ) { ll pre [ n + 1 ] [ k + 1 ] ; ll ans = 0 ; sort ( A . begin ( ) + 1 , A . end ( ) ) ; for ( int i = 1 ; i <= n ; ++ i ) { pre [ i ] [ 0 ] = 1LL ; for ( int j = 1 ; j <= k ; j ++ ) { pre [ i ] [ j ] = A [ i ] * pre [ i ] [ j - 1 ] ; } if ( i != 1 ) { for ( int j = 0 ; j <= k ; ++ j ) pre [ i ] [ j ] = pre [ i ] [ j ] + pre [ i - 1 ] [ j ] ; } } for ( int i = n ; i >= 2 ; -- i ) { for ( int j = 0 ; j <= k ; j ++ ) { ll val = f ( k , j ) ; ll val1 = pow ( A [ i ] , k - j ) * pre [ i - 1 ] [ j ] ; val = val * val1 ; if ( j % 2 == 0 ) ans = ( ans + val ) ; else ans = ( ans - val ) ; } } ans = 2LL * ans ; return ans ; } int main ( ) { int N = 3 ; int K = 3 ; vector < ll > arr = { 1 , 2 , 3 } ; Solution obj ( N , K , arr ) ; cout << obj . pairsPower ( ) << endl ; return 0 ; }