FPS24 I - スコア

考え方

$\prod_{k}(1+a_kx)$ の展開結果の $x^K$ の係数の話であることは明らか。
$x^K$ より後ろを切り捨てながら、畳み込んでいけばよい。

畳み込みは $2$ 個ずつ行うが、長いものを何度も扱うと計算量がかさんでしまう。
残っている中で短い方から $2$ つの積をとることを繰り返して計算量を抑えること。
実装的には、全てを queue にいれてから、前 $2$ つの畳み込みを後ろに入れるループでよい。

この高速化をきちんとすれば、計算量は $O(N\log^2 N)$ である。

入力を受け取る。

n: 3
k: 2
a: {2, 3, 5}

まず、各 $a_i$ から $1+a_ix$ を作り、queue に入れる。
このとき、queue の中身は以下。
$$
[1+2x,\ 1+3x,\ 1+5x]
$$

先頭の $2$ つを畳み込む。
$$
(1+2x)(1+3x)=1+5x+6x^2
$$

これを queue の末尾に入れ、元の $2$ つを取り除く。
queue の中身は以下になる。
$$
[1+5x,\ 1+5x+6x^2]
$$

再び先頭の $2$ つを畳み込む。
$x^K=x^2$ より後ろは切り捨てるので、以下になる。
$$
(1+5x)(1+5x+6x^2)=1+10x+31x^2
$$

これを queue の末尾に入れ、元の $2$ つを取り除く。
最終的な queue の中身は以下。
$$
[1+10x+31x^2]
$$

$x^2$ の係数は $31$ なので、答えは $31$ となる。

特になし。

特になし。