形式的べき級数解説 [多項式・形式的べき級数] （補足）定義や式変形の正当性の確認
この記事は、形式的べき級数の厳密な定義や、その正当性に疑問を感じた場合に見ることを想定しています。次の記事との関係については、どちらが先でも構いません。より手短に面白い所を勉強したり、問題解決に役立てたい場合には、先に（１）（２）（３）な...
maspy
形式的べき級数解説 アルゴリズム・数学 Stirling 数を $p$ で割った余りの計算
概要
下降冪 $(x)_n$、符号つき第 1 種 Stirling 数 $s(n,k)$、第 2 種 Stirling 数 $S(n,k)$ を次で定義します：
$(x)_n = \prod_{0\leq i < n} ...
問題解説 [yukicoder] No.1292 パタパタ三角形
概要
問題文 → ■公式解説 → ■自分の提出 → ■
Fastest AC 記念
解法
まず、正三角形を次のように座標空間内に配置します： $A(1,0,0), B(0,1,0), C(0,0,1)$.
$A$...
AtCoder 天下一折れ線遊戯（天下一プログラマーコンテスト2013 決勝 [E]）
概要
問題文 → ■公式解説 → あるのか不明自分の提出 → ■
解法
LGV 公式を使います。
参考：ABC 216 H 解説（）
可能な線分すべてを考えてしまうと、線分に交差が生じる場合があります（サンプル 3...
AtCoder Get the Salary of Atcoder（square869120Contest #4 [G]）
概要
問題文 → ■公式解説 → ■, p.86自分の提出 → ■
解法
Euler Tour をとって、Euler Tour における頂点順を $x$ 座標、木における深さを $y$ 座標と見なすことで、次のクエリ処理に帰着...
AtCoder 遊園地（みんなのプロコン 2017 [E]）
概要
問題文 → ■公式解説 → ■自分の提出 → ■
公式解説も面白いけど、こっちの方が分かりやすいかな？
解法
解説同様に、次のように辺を張ったグラフを作って強連結成分分解すれば解くことができます。
$i<...
問題解説 [yukicoder] No.1594 Three Classes
概要
問題文 → ■公式解説 → ■自分の提出 → ■
想定されている解法よりもだいぶ難易度が高いですが、$O(N^22^N)$ で解けます。$N \leq 12$ の制約では特に高速にならないですが、この解法であれば $N=20$...
問題解説 [yukicoder] No.925 紲星 Extra
概要
問題文 → ■公式解説 → ■自分の提出 → ■
実装が易しめの平方分割解。あまり他の提出になさそうだったので一応書きます。
解法
列の平方分割により解きます。
数列 $A$ を、長さ $s$ の区間に区切る...
形式的べき級数解説 [多項式・形式的べき級数] 高速に計算できるものたち
前提知識
（１）数え上げとの対応付け（２）式変形による解法の導出（３）線形漸化式と形式的べき級数
上の 3 つの記事では、ほとんど他サイト等を参照せずに私の記事だけで解説を完結させるようにしていましたが、本記事については、この...
AtCoder ギガ国の道路事情（GigaCode 2019 [G]）
概要
問題文 → ■公式解説 → ■自分の提出 → ■
公式解説が読み解けておらず…。
木の圧縮パートを除くと大差ないかもしれません。なかなか実装が大変になってしまいました。
解法
グラフの変形
葉を縮約していき...