yukicoder 1962の解説の解説

writer解説が読解不可能でワロタという話を観測したので読んでみたら俺にも読解不可能でワロタ。

FPSパワーを感じる学びがあったのでまとめる。出典

「全ての要素がiであり、条件を満たすような長さ N の数列の個数」の母関数は $\displaystyle f_i(x):=\sum_{jはiの倍数でない}x^j$ になる。
したがって、「全ての要素が等しく、条件を満たすような長さ N の数列の個数」の母関数は $g(x):=\sum_{i} f_i(x)$ であり、もとの条件を満たすような数列は、このような形の数列を任意個連結したものとして表すことができるので（？）、個数の母関数は $\sum_k g(x)^k=\frac{1}{1-g(x)}$ となる……？
……というのは嘘。これだと例えば $(2,2,2)$ と $(2,2,2)$ を連結して $(2,2,2,2,2,2)$ が作れてしまう。

こういうことが起きる原因は、「全ての要素が i であり、条件を満たすような長さNの数列」のなす集合が連結で閉じていないせい。なので閉じるようにしよう（！）

一般に、あるオブジェクトであって重みNのものの個数の母関数が f であるとき、 $\sum_{k\geq 1}f^k=\frac{f}{1-f}$ は、「オブジェクトを1個以上並べた列であって、重みの和がNになるものの個数」の母関数になる。この概念を悪用する。
あるオブジェクトであって重みNのものの個数の母関数が f であるとき、 $f=\frac{F}{1-F}$ を満たす F は「"それ"を1個以上並べることでオブジェクトを生成する何か」であって重みNのものの個数の母関数になる（？？？）
よって、fのかわりにFで考えることで任意個の連結について閉じるので、あとは前半で述べたのと同じようにして問題が解けた。

正当性はいい感じにやると示せるらしいけど（参考）、もとのオブジェクトを形式的に謎の概念に分解するという考え方はヤバさがあって好き。

この問題は「1のみからなる数列であって条件を満たすもの」「2のみからなる数列であって条件を満たすもの」「3のみからなる数列であって条件を満たすもの」……を同じものが連続しないように並べたいということなので、「"同じもの"が連続しない」という条件をFPSで形式的に処理することができるようになった。すげー

練習のためにいくつか問題を解いてみよう

類題
1以上M以下の整数からなる数列であって、同じ値が連続せず、和がNになるようなものはいくつあるか？
例：(N,M)=(4,3)のとき、(1,2,1),(1,3),(3,1)の3通り

「1」「2」「3」……を同じものが連続しないように並べたいということなので $f_i(x)=x^i$ 、 $F_i=\frac{f_i}{1+f_i}$ 、 $G=\sum_i F_i$ として、 $\frac{1}{1-G}$ が母関数

M=3の母関数　w|a

類題２
1以上M以下の整数からなる数列であって、mod Pが等しい値が連続せず、長さがNの数列はいくつ？
例：(N,M,P)=(3,4,3)のとき、(1or4,2,1or3or4),(1or4,3,1or2or4),(2or3,1or4,2or3),(2,3,1or2or4),(3,2,1or3or4)の26通り

1以上M以下の整数であってmod Pでiになるものの個数をC_iとする。「mod Pで1の数」「mod Pで2の数」「mod Pで3の数」……を同じものが連続しないように並べたいということなので $f_i(x)=C_i x$ 、 $F_i=\frac{f_i}{1+f_i}$ 、 $G=\sum_i F_i$ として、 $\frac{1}{1-G}$ が母関数

(M,P)=(4,3)の母関数　w|a

メモ

yukicoderでゆるふわgolf

yukicoder 1962の解説の解説