Product of Ranges

2 secs 1024 MB

Product of Range 解説

各クエリに対して愚直に掛け算をしていく場合、計算量は $O(NQ)$ となってしまい、間に合いません。ここで、各クエリをより高速に処理する方法を考えます。

ある数列の連続する部分列の総和を高速に処理するアルゴリズムとして累積和が有名ですが、この問題ではその応用として累積積を用います。

具体的には、

S_i = \prod_{k=0}^{i} a_k

を満たす数列 $\{S_N\}$ をあらかじめ計算しておくことで、求める値を

P_{l,r} = \frac{S_r}{S_{l-1}} = S_r\cdot S_{l_1}^{-1}

として求めることができます。

ここで問題となるのがあまりです。この問題は、モジュラ逆数（通称逆元）という概念を用いることで解決できます。（逆元の求め方は長くなるので割愛）

累積和アルゴリズムと同様に、前処理が $O(N)$ 、クエリの計算に $O(Q)$ 、合わせて $O(N+Q)$ でこの問題を解くことができます。

（逆元は、合同式の法 $M$ の大きさに関して対数時間で求められるため、 $M=998244353$ と決まっているこの問題では $O(1)$ とみなすことができます。）

セグメント木を用いると、 $O(Qlog(N))$ で求めることができます。