前置き

こんにちは中学3年生水コーダーのみちらからです。数学が苦手です。

この記事では、形式的冪級数について解説しますが、厳密な定義などは説明せず、できることがなんとなくわかるようになることを目標としています。
ライブラリなどの作り方についても解説はしません。

今回の記事を書いた動機ですが、私が形式的冪級数を勉強したときは、maspyさんのブログを参考にしましたが、私の数学力が足りず、理解にかなり時間がかかってしまいました。
そこで、数学に弱い私だからこそ、私のような一般人にでもわかるような言葉で難しい概念を説明する解説記事を書けるのではないかと思い今回の記事を書くことにしました。(間違っている部分があったらこっそり教えてください)

何ができるの？

まずは例題から見ていきましょう。

長さが$N$の整数からなる数列$A$が与えられる。
最初、みちらから君のスコアは$0$である。
次に、$N$回の操作を行う。
$i$回目の操作では、$0$以上$A_{i}$以下の数字を一つ選んでスコアに加算する。
最終的なみちらから君のスコアが$K$になる組み合わせは何通りあるか出力せよ。

例

$N=2$、$A=[2,2]$、$K=2$とします。
全パターンについて考えてみましょう。

一回目の操作で$0$を選ぶ場合
- 二回目で$0$を選ぶ $\dots$ 和が$0$
- 二回目で$1$を選ぶ $\dots$ 和が$1$
- 二回目で$2$を選ぶ $\dots$ 和が$2$
  この中にスコアが$2$になる選び方は一通りだけあります。
一回目の操作で$1$を選ぶ場合
- 二回目で$0$を選ぶ $\dots$ 和が$1$
- 二回目で$1$を選ぶ $\dots$ 和が$2$
- 二回目で$2$を選ぶ $\dots$ 和が$3$
  この中にスコアが$2$になる選び方は一通りだけあります。
一回目の操作で$2$を選ぶ場合
- 二回目で$0$を選ぶ $\dots$ 和が$2$
- 二回目で$1$を選ぶ $\dots$ 和が$3$
- 二回目で$2$を選ぶ $\dots$ 和が$4$
  この中にスコアが$2$になる選び方は一通りだけあります。

合計で$3$通りの選び方があるので答えは$3$となります。

ここで、突然二次方程式を登場させます。一旦この問題は忘れていてください。
$(x^2+x^1+x^0)(x^2+x^1+x^0)$を展開するとどうなるでしょうか。
$x^2+x^1+x^0$は、$x^2+x+1$になるので、

\begin{align}
&x^2(x^2+x+1)+x(x^2+x+1)+1(x^2+x+1)\\ 
=&(x^2\times x^2+x^2\times x+x^2\times 1)+(x\times x^2+x\times x+x\times 1)+(1\times x^2+1\times x+1\times 1)\\ 
=&(x^4+x^3+x^2)+(x^3+x^2+x)+(x^2+x+1)\\ 
=&x^4+2x^3+3x^2+2x+1
\end{align}

このような形になりました。
これは二つの多項式を掛け算していますが、よく観察すると次のことがわかります。

二つの式から項を一つずつ選ぶ方法全パターンで掛け算をしている
選んだときに掛け算の答えが$x^n$になるものが$x^n$の係数($x^n$の隣についている数字)個ある(例:掛け算の結果が$x^2$になるパターンは$3$つある)

もう一つ、重要な事実として$x^n\times x^m=x^{(n+m)}$があります。
少し見えてきたでしょうか。

ではここで最初の問題の例に戻ってみましょう。例では、最初に$\{0,1,2\}$の中から数字を選び、次に$\{0,1,2\}$の中から数字を選ぶパターンを全探索して、和が$2$になるものの数を数えました。あれ！？！？！？これはこの多項式の掛け算と同じことでは！？！？！？と気づいたあなたは天才です。
この式は、最初の多項式から項を一つ選んで、2つ目の多項式からもう一つ項を選んで掛け算する方法を全探索していて、$x^n\times x^m=x^{(n+m)}$になるわけですから、$x$の累乗の数字に選ぶことが可能な数を入れて、多項式の掛け算をすると、選んだ値の総和が$K$になるパターン数が$x^K$の係数になるわけです。

つまりどういうこと？

多項式を、それぞれの項の$x$の指数に選ぶことが可能な数を入れて作ります。(例:$\{1,3\}$が選べるなら$x^3+x^1$)になる。
それをターン数ぶん繰り返します。
全部掛け算します。
和が$K$になる選び方のパターン数は最終的な$x^K$の係数になります。

豆知識
それまでの操作の式を多項式で割ることによってその操作をなかったことにすることも可能です。(例:ABC321-F)

かんたんだ！！！！！！

練習

長さが$N$の整数からなる数列$A$が与えられる。
最初、みちらから君のスコアは$0$である。
次に、$N$回の操作を行う。
$i$回目の操作では、$A_{i}$をスコアに加算するか、なにもしない。
最終的なみちらから君のスコアが$K$になる組み合わせは何通りあるか出力せよ。

引用元
式は$(1+x^{A_1})(1+x^{A_2})(1+x^{A_3})...(1+x^{A_N})$となります。これの$x^K$の係数が答えです。何も選ばない操作を$x^0$として考えるのに注意しましょう。

$1$から$N$の番号がついたマスが順番に直線上に並んでいる。
みちらからくんは最初マス$1$にいる。
みちらからくんはマス$i$からマス$i+2$もしくはマス$i+3$に移動することができる。
ちょうど$K$回の移動でマス$N$に移動することができる移動方法のパターン数を出力せよ。

引用元
これは少し難しいかもしれませんが、指数を移動した距離、係数をパターン数と考えると解けます。
式は$(x^2+x^3)^K$になり、$x^{N-1}$の係数が答えになります。なぜ$N-1$かというと、理由は単純で、この式だとマスが$0$から始まることになるからです。

さいごに

これで君もFPSマスターだ！！！！
ライブラリは頑張って作ってください(丸投げ)

...え？FFT？知らない子ですね...

誰でもなんとなく理解できる形式的冪級数

前置き

何ができるの？

例

つまりどういうこと？

練習

さいごに