Programa Python3 para productos de rangos en una array

Dada una array A[] de tamaño N. Resolver consultas Q. Encuentre el producto en el rango [L, R] bajo el módulo P (P es Prime). 

Ejemplos:  

Input : A[] = {1, 2, 3, 4, 5, 6} 
          L = 2, R = 5, P = 229
Output : 120

Input : A[] = {1, 2, 3, 4, 5, 6},
         L = 2, R = 5, P = 113
Output : 7 

Fuerza bruta
Para cada una de las consultas, recorra cada elemento en el rango [L, R] y calcule el producto bajo el módulo P. Esto responderá cada consulta en O(N).  

# Python3 program to find
# Product in range Queries in O(N)
 
# Function to calculate Product
# in the given range.
def calculateProduct (A, L, R, P):
 
    # As our array is 0 based 
    # and L and R are given as
    # 1 based index.
    L = L - 1
    R = R - 1
    ans = 1
    for i in range(R + 1):
        ans = ans * A[i]
        ans = ans % P
    return ans
     
# Driver code
A = [ 1, 2, 3, 4, 5, 6 ]
P = 229
L = 2
R = 5
print (calculateProduct(A, L, R, P))
L = 1
R = 3
print (calculateProduct(A, L, R, P))
 
# This code is contributed
# by "Abhishek Sharma 44"

Producción :  

120
6

Eficiente usando el inverso multiplicativo modular:
como P es primo, podemos usar el inverso multiplicativo modular. Usando programación dinámica, podemos calcular una array de preproductos bajo el módulo P tal que el valor en el índice i contiene el producto en el rango [0, i]. De manera similar, podemos calcular el producto pre-inverso bajo el módulo P. Ahora cada consulta se puede responder en O(1). 
La array del producto inverso contiene el producto inverso en el rango [0, i] en el índice i. Entonces, para la consulta [L, R], la respuesta será Producto[R]*Producto inverso[L-1]
Nota: No podemos calcular la respuesta como Producto[R]/Producto[L-1] porque el producto es calculado bajo módulo P. Si no calculamos el producto bajo módulo P siempre existe la posibilidad de desbordamiento.  

# Python3 implementation of the
# above approach
 
# Returns modulo inverse of a with
# respect to m using extended Euclid
# Algorithm. Assumption: a and m are
# coprimes, i.e., gcd(a, m) = 1
def modInverse(a, m):
 
    m0, x0, x1 = m, 0, 1
 
    if m == 1:
        return 0
 
    while a > 1:
 
        # q is quotient
        q = a // m
        t = m
 
        # m is remainder now, process
        # same as Euclid's algo
        m, a = a % m, t
        t = x0
        x0 = x1 - q * x0
        x1 = t
 
    # Make x1 positive
    if x1 < 0:
        x1 += m0
 
    return x1
 
# calculating pre_product array
def calculate_Pre_Product(A, N, P):
 
    pre_product[0] = A[0]
 
    for i in range(1, N):
     
        pre_product[i] = pre_product[i - 1] * A[i]
        pre_product[i] = pre_product[i] % P
 
# Calculating inverse_product
# array.
def calculate_inverse_product(A, N, P):
 
    inverse_product[0] = modInverse(pre_product[0], P)
 
    for i in range(1, N):
        inverse_product[i] = modInverse(pre_product[i], P)
 
# Function to calculate
# Product in the given range.
def calculateProduct(A, L, R, P):
 
    # As our array is 0 based as
    # and L and R are given as 1
    # based index.
    L = L - 1
    R = R - 1
    ans = 0
 
    if L == 0:
        ans = pre_product[R]
    else:
        ans = pre_product[R] * inverse_product[L - 1]
 
    return ans
 
# Driver Code
if __name__ == "__main__":
 
    # Array
    A = [1, 2, 3, 4, 5, 6]
    N = len(A)
 
    # Prime P
    P = 113
    MAX = 100
     
    pre_product = [None] * (MAX)
    inverse_product = [None] * (MAX)
 
    # Calculating PreProduct
    # and InverseProduct
    calculate_Pre_Product(A, N, P)
    calculate_inverse_product(A, N, P)
 
    # Range [L, R] in 1 base index
    L, R = 2, 5
    print(calculateProduct(A, L, R, P))
 
    L, R = 1, 3
    print(calculateProduct(A, L, R, P))
     
# This code is contributed by Rituraj Jain

Producción :  

7
6

¡ Consulte el artículo completo sobre Productos de rangos en una array para obtener más detalles!