Precomputation part , O ( n * k )
for i in range ( 1 , self . n + 1 ) : NEW_LINE INDENT pre [ i ] [ 0 ] = 1 NEW_LINE for j in range ( 1 , self . k + 1 ) : NEW_LINE INDENT pre [ i ] [ j ] = ( self . A [ i ] * pre [ i ] [ j - 1 ] ) NEW_LINE DEDENT if i != 1 : NEW_LINE INDENT for j in range ( self . k + 1 ) : NEW_LINE INDENT pre [ i ] [ j ] = ( pre [ i ] [ j ] + pre [ i - 1 ] [ j ] ) NEW_LINE DEDENT DEDENT DEDENT