載ってないテクニックを募集しています。 前提 と置く。 以降 と書いたらそれは虚数単位ではなく添え字である。 数列 に対し、その DFT を で定義する。 基本事項 以下の事実は式変形で確認できる。 関係式 に対し、 を で定義する。 このとき \begin{align}…

概要 最初空の数列 があり、以下のクエリを処理するアルゴリズムを説明する。 が与えられ、 の末尾に を追加する。 が与えられ、 の xor に関する基底 を出力する。 ただし の highest set bit を と定義したとき は について単調減少である。 時間計算量は…

概要 頂点の木の各頂点にモノイド の元 が乗っているとして、指定されたパス上の値の総積を計算するクエリが、前計算 、クエリ で処理できる。 アルゴリズム 重心分解を行う。 木の重心を とし、各 に対して、 パスから を除いたものに対するクエリ結果を計…