概要 本稿では整数の での逆元について取り扱います。 文中の合同式は です。 拡張ユークリッド互除法で逆元を求める 互除法の手順を高速化できるかもしれないという提案 から の逆元を で計算する 個の数について全ての逆元を で計算する (おまけ) 拡張ユー…

概要 以前記事を書いたのですが消したので別の場所にもう一度書きました。 今度はある程度まともな実装付きです (その分遅いですが)。 Sliding Window Aggregation - data-structures 計算量解析 Queue の場合 ポテンシャル関数を で定義します。 Deque の場…

本記事は皆様からのご指摘を募集しております 誤った記述があるかもしれません 概要 競技プログラミングをやっていると などの表記を見掛けることも多いでしょう *1。 それぞれについて、大雑把な意味をまとめました。 アルゴリズムの挙動の正確な把握は競技…

概要 遅延セグメント木は様々な区間操作が で可能です。 一方で、代入と積の組み合わせは累乗を計算する必要があり、そのままでは に悪化してしまいます。 本稿では空間計算量を に抑えたまま、 で処理する手法を提案します。 また、積に限らず一般のモノイ…

概要 蟻本で 2-SAT のアルゴリズムを最初に見たとき、私はその正当性について何ら疑問を抱きませんでした。 これは私の頭がよく回ったからではなく、単に行間に気づいていなかったからということに最近気づきましたので、反省を兼ねて記録します。 反例のよ…