LoginSignup
67
64

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

Last updated at Posted at 2023-05-20

形式的べき級数(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)。
任意modNTT 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 あり ? ?
67
64
4

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
67
64