多項式のかけ算

2 secs 1024 MB
loop0919's icon loop0919

問題

長さ N+1N+1 の数列 (a0,,aN)(a_0, \cdots, a_N) と長さ M+1M+1 の数列 (b0,,bM)(b_0, \cdots , b_M) が与えられます。
以下の式が xx についての恒等式であるとき、 c0+c1+c2++cN+Mc_0 + c_1 + c_2 + \cdots + c_{N+M} を求めてください。

  • (a0+a1x+a2x2++aNxN)(b0+b1x+b2x2++bMxM)=c0+c1x+c2x2++cN+MxN+M(a_0 + a_1 x + a_2 x^2 + \cdots + a_N x^N)(b_0 + b_1 x + b_2 x^2 +\cdots+b_Mx^M) = c_0 + c_1 x + c_2 x^2 + \cdots + c_{N+M}x^{N+M}

ただし、制約により答えが 64 bit 整数型に収まることが保証されます。

恒等式とは

xx についての恒等式とは、 xx にいかなる値を代入しても常に等式が成り立つ式のことです。

制約

  • 0N,M2×1050 \leq N, M \leq 2 \times 10^5
  • 104ai,bj104-10^4 \leq a_i, b_j \leq 10^4 (0iN, 0jM)(0 \leq i \leq N, \ 0 \leq j \leq M)
  • 入力は全て整数である。

入力

入力は以下の形式で標準入力から与えられる。

NMN \quad M
a0  aNa_0 \ \cdots \ a_N
b0  bMb_0 \ \cdots \ b_M

出力

答えを出力せよ。

サンプル 1

入力
1 2
3 2
2 3 1
出力
30

(3+2x)(2+3x+x2)=6+13x+9x2+2x3(3 + 2x)(2 + 3x + x^2) = 6 + 13x + 9x^2 + 2x^3 です。よって答えは 6+13+9+2=306 + 13 + 9 + 2 = 30 です。

サンプル 2

入力
14 9
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9
0 -1 2 -3 4 -5 6 -7 8 -9
出力
-385

提出


Go (1.21)