考察に使える問題と,実装に使える(=形式的冪級数 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(級)
- HHKB プログラミングコンテスト 2020: F - Random Max
- ACLBC: F - Heights and Pairs
- ABC179: D - Leaping Tak
- ABC178: D - Redistribution
- エイシング プログラミング コンテスト 2020: F - Two Snuke
- ABC171: F - Strivore
- ABC169: F - Knapsack for All Subsets
- ABC159: F - Knapsack for All Segments
- ABC137: F - Polynomial Construction
ARC(級)
- ARC107: D - Number of Multisets
- ARC106: F - Figures
- ARC104: D - Multiset Mean
- NOMURA プログラミングコンテスト 2020: D - Urban Planning
- 第6回 ドワンゴからの挑戦状 予選: C - Cookie Distribution
- diverta 2019 Programming Contest 2: E - Balanced Piles
- Tenka1 Programmer Contest 2019: F - Banned X
- ARC096: E - Everything on It
- ARC059: E - キャンディーとN人の子供
- ARC028: D - 注文の多い高橋商店
簡単な解説
$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(級)
- AGC049: D - Convex Sequence
- AGC046: C - Shift
- AGC045: C - Range Set
- AGC036: C - GP2
- AGC025: B - RGB Coloring
- AGC005: F - Many Easy Problems
簡単な解説
$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)$ 時間で計算できます.