Tích đoạn modular

Hướng tiếp cận

Đặt $p_0=1$ và $p_i=p_{i-1}·a_{i}mod\text{MOD}$ là tích tiền tố modular. Khi đó

$$a_l·a_{l+1}·\dots ·a_r\equiv \frac{p_r}{p_{l-1}}\left(\mathrm{mod}\text{MOD}\right).$$

Vì $\text{MOD}$ là số nguyên tố và $a_i\ne 0$, mọi $p_i\ne 0$ trong $\mathbb{Z}/\text{MOD}\mathbb{Z}$, do đó nghịch đảo $p_{l-1}^{-1}$ tồn tại.

Nhận xét quan trọng

Phép chia thông thường không phù hợp: với tích tiền tố đã lấy modulo, $p_r/p_{l-1}$ trong $\mathbb{Z}$ không cho ra kết quả đúng. Ta phải dùng nghịch đảo modular.

Theo định lý nhỏ Fermat: $x^{\text{MOD}-2}\equiv x^{-1}\left(\mathrm{mod}\text{MOD}\right)$ với mọi $x$ không chia hết cho $\text{MOD}$.

Thuật toán

Có hai cách triển khai:

Cách 1 — Tính nghịch đảo trên từng truy vấn. Với mỗi truy vấn $(l,r)$, tính $\text{inv}=p_{l-1}^{\text{MOD}-2}mod\text{MOD}$ bằng luỹ thừa nhanh, sau đó đáp án là $p_r·\text{inv}mod\text{MOD}$. Mỗi truy vấn mất $O(\log \text{MOD})$.

Cách 2 — Tính trước nghịch đảo (khuyên dùng).

1. Tính tích tiền tố $p_0,p_1,\dots ,p_n$.
2. Tính nghịch đảo của tích tiền tố cuối: ${\text{inv}}_p[n]=p_n^{\text{MOD}-2}mod\text{MOD}$.
3. Suy ngược: ${\text{inv}}_p[i]={\text{inv}}_p[i+1]·a_{i+1}mod\text{MOD}$.

Khi đó mỗi truy vấn được trả lời trong $O(1)$:

$$\text{ans}=p_r·{\text{inv}}_p[l-1]mod\text{MOD}.$$

Độ phức tạp

• Cách 1: $O((n+q)\log \text{MOD})$.
• Cách 2: $O(n+q+\log \text{MOD})$ — chỉ một phép luỹ thừa nhanh duy nhất.

Bộ nhớ: $O(n)$.

Lưu ý cài đặt. Trong C++, dùng long long cho phép nhân vì $a_i,p_i$ có thể đạt ${10}^9$, và tích hai số như vậy cỡ ${10}^{18}$ vẫn nằm trong long long nhưng tràn nếu dùng int.