形式的べき級数解説 FPS Composition and Compositional Inverse (Part 2)
(Part 1) Compositional Inverse and Power Projection(Part 2) Composition Algorithm via Transposition Principle (Here)
...
maspy
形式的べき級数解説 形式的べき級数解説 FPS Composition and Compositional Inverse (Part 1)
(Part 1) Compositional Inverse and Power Projection (Here)(Part 2) Composition Algorithm via Transposition Principle
...
形式的べき級数解説 FPS 合成・逆関数の解説（2）転置原理による合成アルゴリズムの導出
概要
続きです．
前回 → FPS 合成・逆関数の解説（１）逆関数と Power Projection
$f(x), g(x)$ を FPS とするとき，次のどちらかが成り立つ状況で合成 $f(g(x)) = \sum_...
形式的べき級数解説 FPS 合成・逆関数の解説（１）逆関数と Power Projection
概要
noshi91 さんにより，形式的べき級数の合成・逆関数を $\Theta(n\log^2 n)$ 時間で計算する方法が発表されました．
これは基礎的な問題に対して簡潔なアルゴリズムで既知の計算量を改善するもので，国内・...
問題解説 [yukicoder] No.2720 Sum of Subarray of Subsequence of…
概要
問題文 → ■公式解説 → ■自分の提出 → ■
多項式の変数変換を使わずに解きます．
解法
$A_i$ の寄与係数を求めればよいです．左右独立に解けばよいです（これらは公式解説と同じ）．
簡単のため $S$ の先...
Library Checker [Library Checker] Static RMQ
問題概要
問題文 → ■
列が静的（Static）というのは，変更されないということです．静的な列に対する区間 $\min$ クエリに答える問題です．
この記事の読者であればこの問題を簡単に解ける人がほとんどだと思います...
アルゴリズム・数学 グラフ数え上げ
概要
「$N$ 頂点のグラフであって xx を満たすものはいくつありますか？」という種類の問題を扱います．
いわゆる入力定数個の数え上げ問題です．「グラフが与えられるので条件を満たす部分グラフを数えよ」というタイプの問題は扱い...
Library Checker [Library Checker] Enumerate Quotients
問題概要
問題文 → ■
$N$ を正の整数とし，$S = \bigl\lbrace\lfloor N/x\rfloor\mid x\in\lbrace 1,2,\ldots,N\rbrace\bigr\rbrace$ としま...
Library Checker [Library Checker] Range Set Range Composite
問題概要
問題文 → ■
代入操作に特化した場合の区間作用・区間積クエリという問題です．
解法1：遅延セグメント木
ある区間をすべて $a$ で置き換えたときの区間積 $a^n$ は繰り返し二乗法で $O(\log...
Library Checker [Library Checker] Count Points in Triangles
問題概要
問題文 → ■
三角形内部の点の個数を数える問題です．
解法1：愚直解
$4$ 点 $A,B,C,p$ に対して $p$ が $\triangle ABC$ の内部にあるか否かを $\Theta(1)$ ...