高速乗算の実装

以下の実装は誤差が発生せず高速に動作します。

long long multiply(long long x, long long y, long long mod) {
    long long c = static_cast<long long>(static_cast<long double>(x) * y / mod + 0.5);
    c = x * y - c * mod;
    if (c < 0) c += mod;
    if (c >= mod) c -= mod;
    return c;
}

貪欲法の応用

線分関連の問題では、端点をソートしてから処理してみると良い場合があります。

寄与分解の活用

期待値だけでなく、数え上げ問題においても寄与分解が有効です。複雑な問題を単純化する手法として活用できます。

逆順処理

順方向で解けない問題は、逆順で処理してみると解きやすくなる場合があります。

補集合の利用

直接解くのが難しい問題は、不正解のケースを考慮して解くことで解決できる場合があります。

最大値最小化と最小値最大化

最大値最小化や最小値最大化の問題は、二分探索に加えて、貪欲法と微小変更の証明を組み合わせて解くことが有効です。

特に、2つの重みを持つキーを考慮する際は、積・和・商・差・乗をキーとしてソートし、検証することが有効です。

区間の色の確認

区間内のすべての色が存在するかを確認する場合、各位置の直前の色の位置を管理することで、効率的に処理できます。

区間の左端と右端にすべての色をコピーすることで、特例処理を減らすことができます。

k番目の要素

配列上で2つの要素を組み合わせる問題では、特定の要素を固定し、優先度付きキューを用いる方法が有効です。

long long findKthElement(const vector<long long>& arr, int k) {
    priority_queue<pair<long long, int>> pq;
    for (int i = 0; i < k; ++i) {
        pq.push({arr[i], i});
    }
    for (int i = k; i < arr.size(); ++i) {
        auto top = pq.top();
        pq.pop();
        if (arr[i] > top.first) {
            pq.push({arr[i], i});
        }
    }
    return pq.top().first;
}

前駆要素と後続要素の求め方

前駆要素は、値が大きい順にソートし、setで位置を管理することで求められます。

また、カーテシアンツリーを構築し、各点の子木を管理することで、前駆要素と後続要素を効率的に求めることができます。

離散化の最適化

離散化の際、値を保持し、ソートと重複除去を同時に処理することで、計算量を削減できます。

これにより、ソートの計算量をO(log n)に減らすことができます。

小ケの問題

互いに素な正整数a, bについて、ax + by (x, y ≥ 0)で表現できない最大の整数はab - a - bです。

この結果は直接覚えておいた方が実用的です。

約数の数と和

約数の数c₀(ab)と約数の和c₁(ab)を計算する際、以下のような式が有効です。

c₀(ab) = Σ_{i|a} Σ_{j|b} [gcd(i,j)=1]

c₁(ab) = Σ_{i|a} Σ_{j|b} [gcd(i,j)=1] * (a/i * j)

オイラー関数の計算

オイラー関数の計算では、以下の式が有効です。

φ(ab) = (φ(a) * φ(b) * gcd(a,b)) / φ(gcd(a,b))

ビット演算の応用

ビット演算と進位を組み合わせて、特定の問題を効率的に解くことができます。

例えば、整数のビットを逆順にしたTrie木を用意することで、全体に1を加算する操作を効率的に処理できます。

BFSの応用

集合SとTが与えられた場合、Tの各要素についてSの部分集合を検索する問題を、BFSを用いて効率的に解くことができます。

この方法では、各状態を一度しか処理しないため、計算量がO(d2^d)に抑えられます。

動的セグメントツリーの最適化

動的セグメントツリーで遅延伝播が難しい場合、マーカー永続化を用いることが有効です。

マーカーを保持し、クエリ時に経路のマーカーを考慮することで、効率的に処理できます。

分割統治法の改良

分割点が不均等になる場合、左右から分割点を探索することで、計算量をO(n log n)に保つことができます。

区間の逆順対

区間の逆順対を計算する際、ブロック分割を用いることで、O(n√n log n)の計算量で処理できます。

強連結成分の数

強連結成分の数を数える際は、状態圧縮と包含排除原理を組み合わせることが有効です。

具体的には、出次数が0の強連結成分を列挙し、DPで計算します。

動的計画法の最適化

状態数が少ない場合は、メモ化再帰や動的配列を用いたDPが有効です。

状態が連続していない場合、有効な状態を抽出して処理することで、効率を向上させることができます。

区間分割の数え上げ

区間分割の数え上げ問題では、行列累乗を用いてO(log n)で処理できます。

分割の条件が複雑な場合、行列を適切に調整することで、問題を解くことができます。

木上の最近接点

木構造において、各点から最も近い点を求める問題は、DFSを2回行うことで効率的に解けます。

まず、子木の情報を取得し、次に親の情報を用いて子を更新します。

数論の公式

オイラー関数の対称性や、自然数の累乗和の公式を用いることで、数論的な問題を効率的に解くことができます。

特に、φ(n) = n * Π_{p|n} (1 - 1/p)という式は非常に有用です。

生成関数の応用

生成関数を用いることで、複雑な数え上げ問題を効率的に解くことができます。

特に、二項定理や指数生成関数を応用することで、問題を単純化できます。

多項式の計算

多項式のn乗のk階微分を計算する際、組合せ的な解釈を用いることで、効率的に計算できます。

この手法は、生成関数の操作を簡略化するのに有効です。