\(c_i\) は以下のようになる.

\[\begin{align} c_0 &= a_0b_0 \\ c_1 &= a_0b_1 + a_1b_0 \\ c_2 &= a_0b_2 + a_1b_1 + a_2b_0 \\ c_3 &= a_0b_3 + a_1b_2 + a_2b_1 + a_3b_0 \\ \vdots \end{align}\]

これをすべて足すとき, 縦方向の同じ列を見ると,

\[a_0(b_0+b_1+\dots+b_n) \\ a_1(b_0+b_1+\dots+b_{n-1}) \\ a_2(b_0+b_1+\dots+b_{n-2}) \\ \vdots\]

となっている. 括弧の中は累積和を計算しておけば \(O(1)\) で求まるので, 和は \(O(n)\) で計算できる.