競プロ頻出数値表・公式集

サイズ $m$ の集合とサイズ $n$ の集合から合わせて $r$ 個を選ぶ方法は、全体の $m+n$ 個から $r$ 個を選ぶ方法に等しいという恒等式。

パスカルの三角形において、ある列に沿って足し合わせた和が斜め下の値に等しくなる性質。

全体からまず $k_1$ 個を選び、残りから $k_2$ 個、さらに残りから $k_3$ 個というように選んでいく過程に対応している。

$p$ を素数、$x$ を非負整数とする。$r$ を $p$ と互いに素な非負整数として、$x = rp^k$ と書けるとき、以下が成り立つ： $$x \equiv (r \text{ mod } p^e) \times p^k \pmod {p^e}$$

$P$ を置換として、$P(a\ b) = (P(a) P(b))P$ が成り立つ。

$P$ を置換として、$P (a_1\ a_2\ \dots\ a_k) P^{-1} = (P(a_1)\ P(a_2)\ \dots\ P(a_k))$ が成り立つ。

$x + y = x \oplus y + 2 (x \land y)$

$\left\lceil \frac{X}{M} \right\rceil = \left\lfloor \frac{X + M - 1}{M} \right\rfloor$

$\text{round}\left( \frac{X}{M} \right) = \left\lfloor \frac{2X + M}{2M} \right\rfloor$

整数 $X$ の $K$ 進法における $d$ 桁目の数字 (0-indexed):

$\left( \left\lfloor \frac{X}{K^d} \right\rfloor \bmod K \right) = \left\lfloor \frac{X}{K^d} \right\rfloor - K \cdot \left\lfloor \frac{X}{K^{d+1}} \right\rfloor$

頂点がすべて格子点上にある自己交差のない多角形の面積 $S$ は、内部の格子点の数を $I$、周上の格子点の数を $B$ とすると、 $S = I + \frac{B}{2} - 1$ が成り立つ。

有限群 $G$ が集合 $X$ に作用しているとき、同値類（軌道）の個数 $|X/G|$ は、各 $g \in G$ による固定点集合を $X^g = \{ x \in X \mid g \cdot x = x \}$ として、以下が成り立つ。 $$|X/G| = \frac{1}{|G|} \sum_{g \in G} |X^g|$$

平面グラフにおいて、頂点数を $V$、辺数を $E$、独立なサイクルの個数（内側の面の数）を $L$、連結成分の数を $C$ とすると、以下の関係式が成り立つ： $$C = V - E + L$$ （※ サイクルが存在しない森の場合は $L = 0$ となり、$C = V - E$ が成り立つ。）

木の直径の両端点を $u,v$ とすると、$u$ から最も距離が遠い頂点の一つが $v$ であり、逆も同様である。したがって、任意の頂点 $s$ から最も遠い頂点 $u$ を求め、さらに $u$ から最も遠い頂点 $v$ を求めれば、 $u,v$ は木の直径の両端点となり、 $$d(u,v)=\operatorname{diam}(T)$$ が成り立つ。この性質は、辺に非負の重みを付けた重み付き木でも、 距離を辺重みの総和として定義すれば成り立つ。

木 $T$ の頂点 $s$ を一つ固定する。 このとき、直径の両端点を $u,v$ とすれば、そのいずれかは $s$ から最も遠い点である。 なお、これは重み付きでも成立する。

2部グラフ $G = (U \cup V, E)$ において、$U$ のすべての頂点をカバーするマッチングが存在するための必要十分条件は、任意の $S \subseteq U$ に対して $|N(S)| \ge |S|$ が成り立つことである。ここで、$N(S)$ は $S$ に隣接する頂点の集合を表す。

無向グラフ $G$ と開始頂点 $s$ 上で行われる Undirected Vertex Geography において、先手必勝であるための必要十分条件は、$G$ のすべての最大マッチングが頂点 $s$ をカバーすること（すなわち、$s$ を含まない最大マッチングが存在しないこと）である。

多項式 $P(x)$ が $N + 1$ 個の点 $(x_i,y_i)$ を通るときの $P$ の明示的な式。

特に評価点が $x = 0, 1, \dots, N$ のように連続している場合、分母が階乗の積になり、分子の累積積を前計算しておくことで、通常 $O(N^2)$ かかる補間を $O(N)$ に落とすことができます。

$$ \text{達成するまでの回数の期待値} = (\text{1回以上かかる確率}) + (\text{2回以上かかる確率}) + \dots $$