不包含本位置值的累乘数组

[编程题]不包含本位置值的累乘数组

热度指数：3346 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个数组arr，返回不包含本位置值的累乘数组

例如，arr=[2,3,1,4]，返回[12, 8, 24, 6]，即除自己外，其他位置上的累乘

[要求]

时间复杂度为

，额外空间复杂度为

输入描述:

第一行有两个整数N, P。分别表示序列长度，模数(即输出的每个数需要对此取模)
接下来一行N个整数表示数组内的数

输出描述:

输出N个整数表示答案

示例1

输入

4 100000007
2 3 1 4

输出

12 8 24 6

备注:

算法知识视频讲解

Python

嫑葱3Q

N,P = map(int,input().split())
array = list(map(int,input().split()))
l = [0 for _ in range(N+1)]
r = [0 for _ in range(N+1)]
l[0] = 1
r[N] = 1
for i in range(N):
    l[i+1] = l[i] * array[i] % P
for i in range(N-1,-1,-1):
    r[i] = r[i+1] * array[i] % P
answer = []
for i in range(N):
    answer.append(l[i]*r[i+1]%P)
print(' '.join(map(str,answer)))

发表于 2019-09-24 14:26:34 回复(0)