モー隊（Mo's Algorithm）の基礎から応用：平方分割を用いたクエリ処理の最適化
モー隊（Mo's Algorithm）は、範囲クエリをオフラインで効率的に処理するためのアルゴリズムです。本質的には平方分割の考え方を応用したもので、クエリの順序を工夫することで計算量を削減します。
標準的なモー隊
標準的なモー隊は、静的な配列に対する範囲クエリに使用されます。
基本的な考え方
配列をサイズ $B = \frac{n}{\sqrt{m}}$ のブロックに分割します ...
10月27日 13:26 投稿
数論的計算と平方分割を用いた競技プログラミング問題の解説
問題 1：数論的和の計算
この問題では、大きな指数を持つべき乗の和を特定の素数で割った余りを求める必要がある。 naive な快速幂を用いた計算では $O(\sqrt{m} \cdot \log n)$ となり、制限時間を超えてしまう。ここで、法となる数が小さくかつ素数であることに注目する。
フェルマの小定理より、指数部分は法 $p$ に対して $p-1$ で割った余りとして扱ってよい。これに ...
6月1日 04:20 投稿