左右から累積積
N個の数から一つを取り除いたものの積を取りたい 一つ除き積
左からの累積積と右からの累積積を取って、一つ隙間を開けて掛け合わせれば良い
単純にやるとO(N^2)のところがO(N)になる
N=3000で単純解法は3秒掛かるが、この方法なら2ミリ秒
pythondef one_out_product_fast(xs):
N = len(xs)
ret = [1] * N
prod = 1
for i in range(N):
ret[i] = prod
prod *= xs[i]
prod %= MOD
prod = 1
for i in range(N - 1, -1, -1):
ret[i] *= prod
ret[i] %= MOD
prod *= xs[i]
prod %= MOD
return ret
def bluteforce(xs):
N = len(xs)
ret = [1] * N
for i in range(N):
for j in range(N):
if i == j:
continue
ret[i] *= xs[j]
ret[i] %= MOD
return ret:N=3000
%timeit one_out_product_fast(xs)
2.14 ms ± 55 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
%timeit bluteforce(xs)
2.98 s ± 18.2 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]