先日 AtCoder 上で開催された話題の有志コン、 FPS 24 題。
FPS(形式的冪級数) に関する問題を 24 問集めた知の高速道路です。
私も本番参加させて頂き、13完41点という感じでした。
しかしながら、本番では DP、実験エスパー、OEIS、オーバーキルなど種々のズルをしている問題もたくさんあるので、それらと想定解に乖離がある場合や本番で手が届かなかった問題も含めて FPS 24 題で伝えたいことを「ちゃんと」勉強するという本連載を立ち上げました。
1 問 1 記事にする予定のため本連載は 24 回になりそうなもんですが、多分途中何度も逃亡すると思います(ごめんなさい)。また、軽い問題は何問かまとめる可能性もあります。
私は FPS に対して大変疎い(正直、FPS自体かなり競プロじゃないと思ってます)ため、そのような読者にとっては親しみやすい記事になると思います。逆に、 時に厳密さを捨てたり感覚的な理解を伝えたりするので、 FPS に関して深い理解のある方にとっては稚拙な記事になるかもしれません。その場合は優しくご教授頂いたり、誤りを指摘して頂いたり、お帰り頂くなりして頂けると幸いです。
では、始めましょう。
各要素が $1,3,4,6$ である長さ $D$ の数列であって、全要素の和が $N$ であるものはいくつあるか? ${\rm mod}$ $998244353$
$1 \le D \le 2 \times 10^5$
$1 \le N \le 10^6$
本番解法: $(x^1+x^3+x^4+x^6)^D$ を繰り返し二乗法+畳み込みで愚直に計算。時間計算量 $O(N \log^2 N)$ 。
https://atcoder.jp/contests/fps-24/submissions/70656561
なんでこれが $2$ 点の A 問題なんだと一生首を捻っていたが、どうやらオーバーキルらしい。
想定解ベースで再考察すると次の通り。
$(x^1+x^3+x^4+x^6)$ にいい性質がないか探りにかかる。
すると、先ほどの式が因数分解でき、 $x(x^2+1)(x^3+1)$ となる。
欲しいものは $[x^N] (x(x^2+1)(x^3+1))^D$ である。( $[x^k] (x$ の式$)$ で $x$ の $k$ 乗に付く係数を指す)
$[x^N] (x(x^2+1)(x^3+1))^D$
$=[x^{N-D}] (x^2+1)^D(x^3+1)^D$
ここで、何が嬉しいかというと、元々「 $4$ つの和を $D$ 乗する」という扱いにくいものから「 $2$ つの和を $D$ 乗したもの $2$ つの積」というまぁまぁ希望的な形になったことである。
あとは、二項定理を使って $x^2$ が何回かかるかを固定し足し上げればよい。
組み合わせ的解釈を入れると、以下のような感じになる。
以下の行動の部分集合を $D$ ラウンド繰り返す。
- $2$ 円稼ぐ。
- $3$ 円稼ぐ。
$N-D$ 円稼ぐような $D$ ラウンドの過ごし方は何通りか？
こう言われると、 $2$ 円稼ぐのと $3$ 円稼ぐのが独立に扱えているのが嬉しいし、 $2$ 円稼ぐ回数を固定すれば筋良そうに思えるし、現実にそう。この解釈に至るまでに先ほどの式変形を経由している。
https://atcoder.jp/contests/fps-24/submissions/70716720
因数分解を経由して解けるみたいな問題はちょいちょい聞くので、 A からいきなり高度で仰天。先が思いやられる。
