変な用語を普及させてしまってまた怒られそうなので、後世の方が「品目定理ってなんですか！？」になったときのために一応残しておきましょう。 主張 平面内にの pairwise disjoint な長方形3個の配置 が与えられているとします。このときこれは垂直な直線ま…

負の二項定理みたいなやつ $$ \frac 1 { (1 - x ) ^ { 1 + n } } = \sum _ { i \ge 0 } \binom { n + i } i x ^ i $$ 重複組み合わせ $$ \left \lbrace x \in \mathbb{N}^k \ \middle \vert \ x _ 1 + \dots + x _ k = n \right \rbrace = \binom { n + k - …

$$ \newcommand \id { \mathrm { id }} \newcommand \src { \mathrm { src }} \newcommand \tar { \mathrm { tar }} \newcommand \pid { p _ { \id } } $$ 毎回同じ形で出るのになんか混乱するので纏めました。 ※ 「補遺 ～ 執筆後に思ったのですが」にある…

参考文献：文字列の頭良い感じの線形アルゴリズムたち２ - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ 普通の Manacher のアルゴリズム 入力 $s$ の長さが $n$ のとき、普通の Mancher のアルゴリズムは、$A_i$ が $s$ の場所 $s_i$ を中心とし…

参考問題： ABC340-G Leaf Color （鹿島建設プログラミングコンテスト2024） 参考文献： 指定された頂点たちの最小共通祖先関係を保って木を圧縮してできる補助的な木 | Kyopro Encyclopedia of Algorithms LCAをベースに構築するAuxiliary Treeのメモ - 日…