Precomputation part , O ( n * k )
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 ] ; } }