# $[x^c]\prod_{k=1}^{i}(a_k+b_kx)$ を $i=1,2,\dots,N$ について列挙するやつ

この記事の存在自体がとある問題の盛大なネタバレになってしまうけど許して

明らかにNTT-friendly素数 $P$ でmodをとることになるが、それは省略

## 問題設定

$x$ の $1$ 次式が $N$ 個与えられる。$i$ 番目の多項式は $a_i+b_ix$ である。また、非負整数 $c$ が与えられる。

$i=1,2,\dots,N$ について、以下の問いに答えよ。

* $\prod_{k=1}^{i}(a_k+b_kx)$ の $x^c$ の係数は？

## 解法
まず、$\prod_{k=1}^{N}(a_k+b_kx)$ を求める手法は有名であろう。多項式のマージテクとか呼ばれるもので、次数の小さい方から $2$ つを掛け合わせる、を繰り返すことで $O(N\log^2 N)$ で求めたい値が求まる。

与えられる式がすべて $1$ 次式であることを利用して、これをちょっと別の方法でやってみよう。

多項式を順に追加していって、次数が同じ多項式があったらマージする、としてみる。これでも計算量が抑えられることを確認しよう。

次数 $k$ の多項式同士のマージは $O(\frac{N}{k})$ 回発生して、$1$ 回ごとの計算量は $O(k\log k)$ だから、次数 $k$ のマージだけみたときの計算量は $O(N\log k)$ である。$k$ としてありうるものは $N$ 以下の $2$ 冪のみだから、$O(N\log k)$ を雑に $O(N\log N)$ としちゃえば、全体の計算量は $O(N\log^2 N)$ になる。

つまり、stackに多項式を追加していって、先頭 $2$ 項の次数が同じならマージする、としてよい。

このように管理しているstackを $(p_1,p_2,\dots,p_n)$ とする（ $n$ 側が先頭とする）。ここで、$q_i=\prod_{k=1}^{i}p_k$ としたstack $q$ も管理する。ただ、$q_i$ で持つのは、$x^c$ の項とその前の $|p_i|$ 項のみとする。

これがうまくいくことを確かめておこう。$p$ をちゃんと管理していれば、$p$ の隣接する項の次数は同じでなく、しかもすべて $2$ 冪である。つまり $p_i$ の次数は $p_{i+1},p_{i+2},\dots,p_{n}$ の次数の合計より真に大きいから、$|p_i|$ 項さえ持っておけば $x^c$ に寄与しうる箇所はすべて計算できる。

あとはこれがまともな計算量で動くことを確認しておこう。$p_n$ を追加した後、$q_n$ として必要なのは $|p_n|$ 項だけであったから、$q_{n-1}$ の末尾 $2\times|p_n|$ 項だけ拝借して計算すれば $O(|p_n|\log|p_n|)$ で $1$ 回の計算ができる。$p_n$ の長さの合計が $O(N\log N)$ なのはさっきとだいたい同じ感じでわかるから、計算量 $O(N\log^2 N)$ ですべての処理ができることがわかる。