左右から累積積

N個の数から一つを取り除いたものの積を取りたい 一つ除き積

• 左からの累積積と右からの累積積を取って、一つ隙間を開けて掛け合わせれば良い
• 単純にやるとO(N^2)のところがO(N)になる
• N=3000で単純解法は3秒掛かるが、この方法なら2ミリ秒 python

def 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)

https://github.com/nishio/atcoder/blob/master/memo/one_out_product.py