AtCoderで解ける形式的べき級数問題を集めました

形式的べき級数(FPS)を勉強するべく、AtCoderでFPSを使って解ける問題を集めました。多項式も含みます。

公式解説・ユーザ解説にFPS解法がない問題は、有志の解説を探してリンクしました。

これらの問題でVirtual Contestを作りました。ご自由に参加下さい。
https://kenkoooo.com/atcoder/#/contest/show/accf2cb4-2dc4-402e-994a-055fd9297203

形式的べき級数って何？という方は、以下の記事を読むとよいです。
誰でもなんとなく理解できる形式的冪級数 みちらからさん
形式的べき級数解説 maspyさん
【競プロer向け】母関数を習得しよう！ tatyamさん

一覧にないFPS問題を見つけた方は是非教えて下さいませ。

一覧表の各列の意味は以下の通りです。

diff

atcoder problemsのdifficultyの値です。diffのない問題は atcoder-standings-difficulty-analyzer で推定された値を使っています。問題はdiff順に並べました。

解説

公式解説・ユーザ解説にFPS解法があるかを表します。

diff変化

必要なFPS知識とその典型的な使い方を知っていることで、diffがどう変わるかを、私の解いた問題のみ、主観でラベル付けしました。FPS知識自体の難しさは含まれません。典型化・易化・同等・難化 の4種類＋（発展）です。（発展）は、FPSにより発展的な解法（計算量が落ちるなど）が可能になる問題であるため、ラベル付け対象外としました。

知識

FPS解法に必要な知識です。高校数学まででは学ばないものを記載しています。▶ボタンをクリックすると表示されます。複数必要な場合、難易度の低い知識は省略しています。カッコ内は、発展的な解法でのみ必要になる知識です。

知識欄に記載される代表的なものの説明を以下に書いておきます。（▶ボタンクリックで説明表示）

なし

高校数学までで学ぶ内容のみで解けるもの。多項式の計算、等比数列の和、二項定理など。

割り算

分母をDPにするテク。tatyamさん記事 参照。逆元を使う方法と対比して「疎な場合の高速化」と呼ばれることもある。

負の二項定理

分母に、二項のみの式の累乗がある時に計算できる。 $ \frac{1}{(1-x)^n} = \sum {}_n\textrm{H}_i x^i = \sum \binom{n+i-1}{i} x^i $

畳み込み

積は畳み込みなので、畳み込みの高速計算法（FFTやNTT）で $O(N\log N)$ になる。ACLにあり(convolution)。

任意mod

NTT friendlyではないmod（$10^9+7$ 等）で高速畳み込みする方法。3つのNTT friendlyなmodで計算し、復元する。 参考

逆元

$1/f$ を $O(N\log N)$ で求めるテク。 参考

多項式の総積

次数の低い多項式が複数あり、全て積を取る時の高速化。「次数の低いものを2つ選び、積を取る」を多項式が1つになるまで繰り返すと、 $O(N\log ^2 N)$ 。厳密に次数最小の2つでなくても、「バッファの先頭2つを取り出し、積を取ってバッファ末尾に戻す」を繰り返すだけでも $O(N\log ^2 N)$ になり、実装が楽。

疎な場合の高速化(累乗、exp等)

非0な係数が少ない時の高速化。参考： こちら の「疎な場合の高速化」「疎な場合の高速化 (2)」「疎な微分方程式」

Bostan-Mori法

$f/g$ の $x^K$ の係数が $O(N\log N \log K)$ で求まる。 $K$ が巨大でもOK。 参考

Berlekamp–Massey法

線形漸化式と分かっている時、数列の最初の何項かから漸化式を求めるアルゴリズム。$d$ 項間漸化式の時 $O(d^2)$ 。 参考（ちゃんと理解していない）

指数型母関数

$\sum a_i \frac{x^i}{i!}$ の形の母関数を使うテク。習得難易度高い。 参考1 参考2

問題名・リンク	diff	解説	有志の解説	diff変化	知識
Typical DP Contest A - コンテスト	525	なし	はたむさん	同等	なし
AtCoder Beginner Contest 245 D - Polynomial division	815	なし	けんちょんさん	同等	割り算、（逆元）
AtCoder Beginner Contest 178 D - Redistribution	875	あり	maspyさん・はたむさん	典型化	割り算、（逆元）、（任意mod）
AtCoder Beginner Contest 179 D - Leaping Tak	1251	あり	けんちょんさん・maspyさん・はたむさん	典型化	割り算、（逆元）
AtCoder Beginner Contest 135 D - Digits Parade	1334	なし	maspyさん	(発展)	（疎な場合の累乗）、（任意mod）
Educational DP Contest / DP まとめコンテスト I - Coins	1588	あり		易化	なし、（多項式の総積）、（FFTでの畳み込み）
AtCoder Beginner Contest 169 F - Knapsack for All Subsets	1698	なし	けんちょんさん・maspyさん	易化	なし、（分割の数え上げ(1)）
AtCoder Regular Contest 116 D - I Wanna Win The Game	1718	なし	hamamu	易化	なし、（畳み込み）
AtCoder Grand Contest 025 B - RGB Coloring	1739	なし	optさん	易化	なし
AtCoder Beginner Contest 154 F - Many Many Paths	1775	あり	けんちょんさん	同等	負の二項定理
AtCoder Beginner Contest 171 F - Strivore	1795	あり	maspyさん	易化	負の二項定理
AtCoder Beginner Contest 159 F - Knapsack for All Segments	1876	あり	maspyさん	易化	なし
AtCoder Beginner Contest 305 G - Banned Substrings	1989	あり		(発展)	（Berlekamp–Massey法）、（Bostan-Mori法）
Educational DP Contest / DP まとめコンテスト M - Candies	2015	あり	けんちょんさん・maspyさん・はたむさん	典型化	畳み込み or 割り算、（exp,logの利用）
AtCoder Regular Contest 110 D - Binomial Coefficient is Fun	2078	あり	けんちょんさん	典型化	負の二項定理
AtCoder Regular Contest 059 E - キャンディーとN人の子供	2189	なし	optさん	典型化	なし
AtCoder Regular Contest 067 E - Grouping	2190	なし	バイトさん	典型化	指数型母関数
AtCoder Beginner Contest 009 D - 漸化式	2213	なし	けんちょんさん	(発展)	（Bostan-Mori法）
AtCoder Regular Contest 104 D - Multiset Mean	2251	あり	けんちょんさん	易化	割り算
Typical DP Contest F - 準急	2253	あり	optさん	易化	割り算
AtCoder Beginner Contest 215 G - Colorful Candies 2	2276	あり		(発展)	（Polynomial Taylor Shift）
AtCoder Beginner Contest 276 G - Count Sequences	2278	あり		典型化	負の二項定理
AtCoder Beginner Contest 281 G - Farthest City	2304	あり		(発展)	（i乗和のiに関する列挙）
Xmas Contest 2022 D - Dichotomy	2401	あり		難化	Catalan’s Convolution Formula
AtCoder Beginner Contest 259 Ex - Yet Another Path Counting	2406	あり		(発展)	（負の二項定理）
AtCoder Beginner Contest 180 F - Unbranched	2419	あり	kaichou243さん	典型化	指数型母関数、exp、（疎な場合のexp）
AtCoder Beginner Contest 267 Ex - Odd Sum	2422	あり		同等	畳み込み、（多項式の総積）、（exp,logの利用）
AtCoder Beginner Contest 279 G - At Most 2 Colors	2431	あり		?	?
AtCoder Regular Contest 140 D - One to One	2443	あり		?	?
AtCoder Regular Contest 144 D - AND OR Equation	2468	あり		?	?
AtCoder Regular Contest 160 D - Mahjong	2485	あり	けんちょんさん	?	?
AtCoder Beginner Contest 303 Ex - Constrained Tree Degree	2501	あり	けんちょんさん	?	?
ACL Beginner Contest F - Heights and Pairs	2545	あり		?	?
AtCoder Beginner Contest 231 G - Balls in Boxes	2606	あり		?	?
AtCoder Beginner Contest 213 G - Connectivity 2	2663	あり	maspyさん	?	?
HHKB プログラミングコンテスト 2020 F - Random Max	2691	なし	けんちょんさん	?	?
aising2020 F - Two Snuke	2742	あり	tatyamさん	?	?
AtCoder Regular Contest 106 F - Figures	2755	あり	けんちょんさん・maspyさん	?	?
AtCoder Beginner Contest 253 Ex - We Love Forest	2758	あり		?	?
灘校文化祭コンテスト 2022 Day1 K - Li	2780	あり		?	?
AtCoder Beginner Contest 221 H - Count Multiset	2793	あり		?	?
AtCoder Beginner Contest 213 H - Stroll	2806	あり		?	?
AtCoder Beginner Contest 226 H - Random Kth Max	2813	あり		?	?
AtCoder Beginner Contest 297 Ex - Diff Adjacent	2855	あり		?	?
AtCoder Beginner Contest 241 Ex - Card Deck Score	2881	あり		?	?
AtCoder Beginner Contest 236 Ex - Distinct Multiples	2898	あり		?	?
第5回 ドワンゴからの挑戦状 予選 E - Cyclic GCDs	2978	あり	けんちょんさん	?	?
AtCoder Regular Contest 028 D - 注文の多い高橋商店	2997	あり	maspyさん	?	?
競プロ典型 90 問 090 - Tenkei90's Last Problem（★7）	3000?	あり	かつっぱさん動画	?	?
AtCoder Beginner Contest 309 Ex - Simple Path Counting Problem	3029	あり		?	?
AtCoder Regular Contest 012 D - Don't worry. Be Together	3046	あり	maspyさん	?	?
AtCoder Beginner Contest 225 H - Social Distance 2	3061	あり		?	?
AtCoder Grand Contest 065 D - Not Intersect	3117	あり		?	?
AtCoder Beginner Contest 270 Ex - add 1	3159	あり		?	?
AtCoder Beginner Contest 269 Ex - Antichain	3178	あり		?	?
AtCoder Beginner Contest 281 Ex - Alchemy	3180	あり	けんちょんさん	?	?
AtCoder Beginner Contest 285 Ex - Avoid Square Number	3192	あり		?	?
AtCoder Beginner Contest 300 Ex - Fibonacci: Revisited	3209	あり	けんちょんさん	?	?
AtCoder Beginner Contest 289 Ex - Trio	3246	あり		?	?
AtCoder Regular Contest 124 F - Chance Meeting	3246	あり		?	?
AtCoder Beginner Contest 279 Ex - Sum of Prod of Min	3279	あり		?	?
AtCoder Beginner Contest 288 Ex - A Nameless Counting Problem	3282	あり		?	?
パ研合宿2023　第3日「Teamwork」 A - ABC	3305	あり		?	?
AtCoder Regular Contest 137 F - Overlaps	3313	あり		?	?
AtCoder Beginner Contest 260 Ex - Colorfulness	3339	あり		?	?
AtCoder Beginner Contest 345 G - Sugoroku 5	3343	あり		?	?
Typical DP Contest T - フィボナッチ	3346	あり	けんちょんさん	?	?
第一回日本最強プログラマー学生選手権-予選- F - Candy Retribution	3353	あり	maspyさん	?	?
AtCoder Regular Contest 140 F - ABS Permutation (Count ver.)	3392	あり		?	?
AtCoder Grand Contest 060 D - Same Descent Set	3394	あり		?	?
square869120Contest #3 G - フィボナッチ数の総和	3431	あり	maspyさん	?	?
AtCoder Grand Contest 013 E - Placing Squares	3455	なし	maspyさん	?	?
AtCoder Beginner Contest 257 Ex - Dice Sum 2	3461	あり		?	?
灘校文化祭コンテスト 2022 Day2 O - Simple Inversion Problem	3472	あり		?	?
AtCoder Beginner Contest 222 H - Beautiful Binary Tree	3477	あり		?	?
パ研合宿2022　第3日「teamwork」 K - Inner Product	3479	あり		?	?
Kyoto University Programming Contest 2019 K - One or All	3484	あり	maspyさん	?	?
AtCoder Beginner Contest 230 H - Bullion	3528	あり		?	?
AtCoder Regular Contest 134 F - Flipping Coins	3530	あり(一言だけ)		?	?
AtCoder Regular Contest 136 F - Flip Cells	3554	あり		?	?
AtCoder Regular Contest 154 F - Dice Game	3616	あり		?	?
AtCoder Regular Contest 156 E - Non-Adjacent Matching	3650	あり		?	?
灘校文化祭コンテスト 2022 Day2 P - Turn it Over	3654	あり		?	?
AtCoder Beginner Contest 272 Ex - Flipping Coins 2	3740	あり		?	?
AtCoder Beginner Contest 278 Ex - make 1	3768	あり		?	?
Toyota Programming Contest 2023 Spring Final E - East-Northeast	3769	あり		?	?
AtCoder Regular Contest 146 F - Simple Solitaire	3820	あり		?	?
AtCoder Regular Contest 139 F - Many Xor Optimization Problems	3893	あり		?	?
AtCoder Regular Contest 133 F - Random Transition	3905	あり		?	?
AtCoder Regular Contest 145 F - Modulo Sum of Increasing Sequences	3943	あり		?	?
AtCoder Regular Contest 167 F - Tree Tree Tree	3951	あり		?	?
AtCoder Regular Contest 147 F - Again ABC String	4016	あり		?	?
AtCoder Grand Contest 062 E - Overlap Binary Tree	4233	あり		?	?
AtCoder Regular Contest 155 F - Directable as Desired	9999	あり		?	?
AtCoder Regular Contest 120 F2 - Wine Thief	9999	あり		?	?
AtCoder Regular Contest 173 F - Select and Split	9999	あり		?	?
AtCoder Grand Contest 053 F - ESPers	9999	あり		?	?
AtCoder Grand Contest 064 F - No Permutations	9999	あり		?	?