左右から累積積

左からの累積積と右からの累積積を取って、一つ隙間を開けて掛け合わせれば良い

単純にやるとO(N^2)のところがO(N)になる

N=3000で単純解法は3秒掛かるが、この方法なら2ミリ秒

code:python

def one_out_product_fast(xs):

N = len(xs)

prod = 1

for i in range(N):

prod %= MOD

prod = 1

for i in range(N - 1, -1, -1):

prod %= MOD

return ret

def bluteforce(xs):

N = len(xs)

for i in range(N):

for j in range(N):

if i == j:

continue

return ret

code::

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)