概要
競技プログラミングの強そうな人が使っている印象がある「形式的冪級数」。よくわかりませんが、名前がかっこいいので使ってみたいです。
形式的冪級数を使うにあたって、大変素晴らしいライブラリも公開していただけています。感謝しながら使っていきます。optさんありがとう。
問題リストもあります。すごい。これを参考にして形式的冪級数を使って問題を解きながら、理解を深めていこうと思います。
問題リストをAtcoder-problemsのVirtual contestに登録してみました。コンテストは2030年に終了しますので、それまでに頑張りましょう。
本題
急に問題を見ても立式できないことが多かったので、以降にメモを残していきます。
各問題のメモ
TDPC-A コンテスト
準備運動。
https://atcoder.jp/contests/tdpc/tasks/tdpc_contest
概要
$N (\leq 100)$問ある問題の$i$番目は$p_i(\leq 100)$点。合計得点は何通りか。
立式
合計$k$点として、$T^k$の係数が非ゼロな$k$の個数を数えればいいです。
f(T) = (1 + T^{p_1})(1+T^{p_2})\ldots(1+T^{p_N})
↑を展開して、係数が非ゼロの個数を数えます。
提出
これは簡単。
EDPC-M - Candies
これも準備運動。
概要
$N (\leq 100)$人に飴$K (\leq 10^5)$個を配る。$i$番目の人には$0\sim a_i$個配る。配り方は何通りか？
立式
$i$番目の人への配り方は、↓の多項式$f_i$に対応させます。
f_i = 1 + T + T^2 + ... + T^{a_i} = \frac{1 - T^{a_i + 1}}{1 - T}
全員分を掛け算した$F = f_1 f_2 f_3 \ldots f_N $ の、$T^{K}$の係数が答えです。
提出
TDPC F-準急
これ、DPでも解きたいのですが、頭が混乱します。
概要、立式
optさんが書いてくれているので省略。賢い。
提出
スッキリです。
ABC179 D - Leaping Tak
DP+imos法で、区間更新的なことをする問題だった気がします。
https://atcoder.jp/contests/abc179/tasks/abc179_d
概要
1マス目から$N(\leq 2 \times 10^5)$マス目まで進む。
1回の移動の際には、K個の区間 $[L_1, R_1]$, $[L_2, R_2]$, $\ldots$, $[L_K, R_K]$から1つ数字を選び、その数だけ進む。$N$マス目までの進み方は何通り？
立式
1回の移動を、↓の多項式$f$に対応させます。$[L_i, R_i]$の次数の項で、係数を1にします。
\begin{align}
f &= T^{L_1} + T^{L_1+1} + ... + T^{R_1}\\
&+ T^{L_2} + T^{L_2+1} + ... + T^{R_2} \\
&+ ... \\
&+ T^{L_K} + T^{L_K + 1} + ... + T^{R_K}
\end{align}
何回か移動するので、それを表す多項式$F$は↓。
F = 1 + f + f^2 + ... = \frac{1}{1-f}
$N-1$マス進むので、↑の$T^{N-1}$の係数が答えです。簡単に表現できて嬉しい。
元の問題には$K\leq 10$という制約がありますが、この解き方だと不要ですね。すごい。
提出
10行くらい。助かります。
ABC178 D - Redistribution
高校受験でよくやる、ボールと仕切りで考える問題ですよね。
概要
全ての項が3以上の整数である数列であって、その総和が Sであるような数列は、何通りあるか？($10^9+7$で割った余り)
立式
慣れてきました。1つの項に対応する多項式は、↓。
f = T^3 + T^4 + ... = T^3 ( 1 + T + ...) = \frac{T^3}{1-T}
$f$, $f^2$, $f^3$, ... の、$T^S$の係数の和が答えになるので、まとめて考えればいいです。
F = f + f^2 + f^3 + ... = \frac{f}{1-f}
$T^S$の係数が答え。
提出
7行くらい。
まとめ
DPを書いてバグらせて時間が溶ける...のが悲しいので、形式的冪級数でシュッと解いていきたいですね！
感謝を込めてもう一度リンクを貼ります。ありがとうございました
つづき：