COmPoUNdS 最后更新于 2025-05-01 18:22:21

首先找一个素数 $p$ 使得存在 $\omega$ 使得 $\omega^k\equiv 1\pmod p$（如果 $k\mid(p-1)$，$g$ 是 $p$ 的原根，则一组解是 $\omega\equiv g^{(p-1)/k}\pmod p$）。接下来可以在 $\mathbb F_p$ 上操作。 那么把序列中的每个数 $x$ 换成 $\omega^x$，这样 1 操作就变成区间乘 $\omega^c$，2 操作仍然是判断子段相等。写一个支持区间乘、求区间 Hash 值的线段树即可。 时间复杂度 $O(n+q\log n)$。