競プロでたまに出てくるけど忘れがちな定理・公式などをまとめる予定です。
クリックで開くよ

（まだ下書き中）

定理

数え上げ系

行列木定理

問題例

$n$ 頂点 $m$ 辺のグラフの（ラベル付き）全域木はいくつありますか。

答え

ラプラシアン行列の任意の余因子の行列式の $(-1)^{i+j}$ 倍

ピックの定理

問題例

格子点を頂点とする穴のない多角形の内部にある格子点の個数を $i$ 、辺上にある格子点の個数を $b$ とするとき、この多角形の面積は？

答え

$S=i+\displaystyle\frac{1}{2}b-1$

LGV 公式

問題例

DAG（有向無閉路グラフ）および始点集合 $A$ と終点集合 $B$ が与えられる。 $A$ と $A$ が整合的（※）であるとき、これらを始点・終点とするパスの組であって、どの 2 つのパスも頂点を共有しないものの数はいくつあるか。

整合的とは

2 つの始点 $a_{i} < a_{j} \in A$ と2 つの終点 $b_{i} > b_{j} \in B$ があるとき、 $a_{i}$ から $b_{j}$ のパスと $a_{j}$ から $b_{i}$ のパスは必ず交わる

答え

$x_{i,j}$ を $a_{i}$ から $b_{j}$ に向かうパスの個数とすると $X=(x_{i,j})$ の行列式 https://atcoder.jp/contests/abc216/editorial/2561

Lucas の定理

問題例

$_{m}C_{n}$ は $\mod p$ で

答え

$_{m}C_{n} \equiv \displaystyle\prod_{i=0}^{k} {_{m_{i}}C_{n_{i}}} \mod p$

ただし $m_{i}$ は $m$ の $p$ 進法表記の下から $i$ 桁目

BEST theorem

問題例

オイラーグラフ $G$ に含まれるオイラー閉路の個数は？

答え

$c(G, v) \cdot \displaystyle\prod_{w \in V} (\mathrm{outdeg}(w) - 1)!$

ここで $c(G, v)$ は頂点 $v$ を根とする有向全域木(全ての辺が根の方を向いている全域木) の個数 (実は $c(G,v)$ の値は $v$ によらず一定なので $v$ は任意にとって良い)、 $V$ は $G$ の頂点集合、 $\mathrm{outdeg}(w)$ は頂点 $w$ の出次数である。

（ Editorial - AtCoder Beginner Contest 336 より抜粋）

グラフ関係

Dilworth の定理

問題例

Dilworth の定理の主張をグラフの用語で言ってみてね。

答え

DAG 上の最小 path 被覆（全ての頂点を適当な path に属するようにして分割する時の必要な path の最小本数）は、最大 antichain（頂点の集合であって、集合に属する任意の 2 頂点に関して、それらを結ぶような path が存在しない）の要素数と一致する
ABC 134-E の解説より

ちなみに 2 部グラフ上の最大独立集合は「頂点数マイナス最大マッチング」なのでこれが関係する問題もある（ABC 137-Ex の解説）。

Erdős–Gallai の定理

問題例

有限整数列 $d_{1},\ \cdots,\ d_{n}$ が無向グラフの次数列（頂点の次数を降順に並べたもの）になる条件は？

答え

総和が偶数かつ $\sum _{i=1}^{k}d_{i}\leq k(k-1)+\sum _{i=k+1}^{n}\min(d_{i},k)$

Tutte 行列

問題例

$(V, E),\ V = \{1,\ \cdots,\ n\}$ に完全マッチングが存在する条件

答え

$A_{ij}={\begin{cases}x_{ij}\;\;{\mbox{if}}\;(i,j)\in E{\mbox{ and }}i \lt;j\\-x_{ji}\;\;{\mbox{if}}\;(i,j)\in E{\mbox{ and }}i \gt;j\\0\;\;\;\;{\mbox{otherwise}}\end{cases}}$
で表される $n \times n$ 行列の行列式が（多項式として）ゼロ

証明系（？）

結婚定理

問題例

略

答え

略

LP 双対

問題例

弱双対性・強双対性

答え

弱双対性： $\max \{𝑐𝑥\ |\ 𝑥 \ge 0,\ 𝐴𝑥 \le 𝑏\} \le \min \{ 𝑦𝑏\ |\ 𝑦 \ge 0,\ 𝑦𝐴 \ge c\}$
強双対性： $\max \{𝑐𝑥\ |\ 𝑥 \ge 0,\ 𝐴𝑥 \le 𝑏\} = \min \{ 𝑦𝑏\ |\ 𝑦 \ge 0,\ 𝑦𝐴 \ge c\}$
hos さんのスライド 79 ページ付近から

母関数関係

ラグランジュの反転公式

問題例

$F$ と $G$ が互いに逆関数である（すなわち $G(F(x))=F(G(x))=x$ ）とき $\lbrack x^n \rbrack G(x)$ を $F(x)$ で表してね。

答え

$\lbrack x^n \rbrack G(x) = \frac{1}{n} \lbrack x^{n-1} \rbrack \left(\frac{x}{F(x)}\right)^n\$
ABC 222-H の解説

Multiset

問題例

$\mathcal{B} = \mathrm{MULTISET}(\mathcal{A})$ が $\mathcal{A}$ の多重集合の構造のとき、母関数 $B(x)$ を $A(x)$ で表してね。

答え

$B(x) = \exp \left(\sum_{0 \lt k} \frac{A(x^k)}{k} \right)$
ABC 230-H の解説

文字列関係

繰り返し文字列

問題例

$X, Y$ を空でない有限文字列とするとき、次を有限文字列の条件・式で答えよ。
① $X^{\infty}=Y^{\infty}$ と同値な条件は？
② $X^{\infty} \neq Y^{\infty}$ のとき $\mathrm{lcp}(X^{\infty}, Y^{\infty})$ は何と等しい？
③ $X^{\infty} \lt Y$ と同値な条件は？

答え

① $X^{\infty}=Y^{\infty} \iff XY=YX$
② $\mathrm{lcp}(X^{\infty}, Y^{\infty}) = \mathrm{lcp}(XY, YX)$
③ $X^{\infty} \lt Y \iff XY \lt Y$
ARC 175-F の解説
noshi さんのべき級数による証明