div2by1というアルゴリズムがある -> https://gmplib.org/~tege/division-paper.pdf これはBarrett reductionやMontgomery乗算と違い、 (k, k) -> 2k-bitの乗算器でk-bitの剰余算ができる(Barrett reductionは(2k, 2k) -> 4k-bitの乗算器を必要とする) modが…

問題 長さNの整数列a_iが与えられます $Q$個のクエリを処理してください given l, r, x: $a_l \cdots a_r$を$x$倍 given l, r: $a_l \times a_{l+1} \times \cdots \times a_r \bmod 998244353$を出力 $O(\log N)$ per queryで解けるがおそらく$O( \log^{2} …