多項式のかけ算

解説

愚直に多項式の積を求めてその係数の総和を求めると、$O(NM)$ の計算量が必要になり、間に合いません。

そこで、以下の事実を使う必要があります。

• 多項式 $f(x)$ の係数の和は $f(1)$ である。

よって、

$\begin{aligned} c_0 + c_1 + c_2 + \cdots + c_{N+M} &= (a_0 + a_1 \cdot 1 + a_2 \cdot1 + \cdots + a_N \cdot 1)(b_0 + b_1 \cdot 1 + b_2 \cdot 1 + \cdots + b_M \cdot 1) \\ &= (a_0 + a_1 + a_2 + \cdots + a_N)(b_0 + b_1 + b_2 + \cdots + b_M) \end{aligned}$

となるため、 $a$ の総和と $b$ の総和をかけることで $O(N+M)$ で解くことができます。

想定解