形式的冪級数(FPS)が使える AtCoder の問題リスト(随時更新)

考察に使える問題と,実装に使える(=形式的冪級数 or 多項式ライブラリが使える)問題の両方が混ざっています.

自分の記憶のみに頼って列挙したので,大量に漏れがあると思います.思い出したら or 新たな問題に出会ったら随時更新します.他にも形式的冪級数が使える問題を見つけたら教えてくださると嬉しいです.

演習効果が高そうな問題は,簡単に解法を書きます.

FPS ライブラリの実装例はこちらの記事を参照してください:

Unrated コンテスト

簡単な解説

$1$ 駅以上 $K$ 駅未満連続して止まることと,$1$ 駅以上連続して止まらないことを交互に繰り返します.そこで,$z$ を不定元とする冪級数を\begin{align*}f := \sum_{i=1}^{K-1} z^i &= \frac{z - z^K}{1 - z},\\ g := \sum_{i=1}^{\infty} z^i &= \frac{z}{1 - z} \end{align*}と定めると,問題の答えは,\begin{align*} f + fgf + fgfgf + \cdots &= \frac{f}{1-fg} \\ &= \red{\frac{(1-z)(z - z^K)}{1 - 2z + z^{K+1}}} \end{align*}の $z^N$ の係数に等しいです(途中計算は Wolfram Alpha に投げるとよいです).これは「係数がスパースな冪級数用の乗除算」を使うことで,計算量 $O(N)$ で計算できます.

ABC(級)

ARC(級)

簡単な解説

$z$ を不定元とする冪級数を\[g_i(x_i) := \sum_{a=0}^\infty (x_i z)^a = \frac{1}{1 - x_i z}\]と定めると\[f(x_1, \dots, x_N) = [z^C] \prod_{i=1}^N g_i(x_i) \]です.よって問題の答えは,\begin{align*} \sum_{x_1,\dots,x_N} f(x_1,\dots,x_N) &= [z^C] \sum_{x_1,\dots,x_N} \prod_{i=1}^N g_i(x_i) \\ &= \red{[z^C] \prod_{i=1}^N \bigg( \sum_{x_i = A_i}^{B_i} g_i(x_i) \bigg)} \end{align*}となります.これを愚直に計算すると計算量は $O(NC(C + \max_i B_i))$ となり,十分高速です.

AGC(級)

簡単な解説

$z$ を不定元とする多項式を $f := z^0 + z^A + z^B + z^{A+B}$ と定めると,問題の答えは $[z^K] f^N$ です.これの計算は一見難しそうですが,$f$ をぐっと睨むと,$f = (1 + z^A)(1 + z^B)$ と因数分解できることに気づきます.よって,二項定理を使うと\begin{align*} [z^K]f^N &= [z^K] \bigg ( \sum_{x = 0}^N \binom{N}{x} z^{Ax} \bigg) \bigg ( \sum_{y = 0}^N \binom{N}{y}z^{By} \bigg) \\ &= \red{\sum_{(x, y):\, Ax + By = K} \binom{N}{x} \binom{N}{y}} \end{align*}と変形でき,これは $O(N)$ 時間で計算できます.

有志コンテスト

タイトルとURLをコピーしました