1987 . 多項式乘法
TopCoder
Tags
Description
這題就是所謂的多項式乘法。給你兩個多項式$f(x)=\sum_{i=0}^ {N}{a_i x^ i}$、$g(x)=\sum_{i=0}^ {M}{b_i x^ i}$，請你輸出$f(x)g(x)$展開之後的結果。
Input Format
本題沒有輸入，如果你輸入了任何東西，可能會導致各種不可預期的結果。
請#include "lib1987.h"之後實作下列一個函數。
void multiply(int N, int M, long long a[], long long b[], long long ans[]);：傳入非負整數N、M分別代表$\deg f$和$\deg g$；a、b分別為長度為$N+1,M+1$的陣列，代表$f(x)$和$g(x)$的係數。你要將$f(x)g(x)$的係數存入ans陣列當中。（係數皆升冪排列；ans陣列的大小是$N+M+1$。）
對於所有測資，$N, M\leq 10^ 6; |a_i|, |b_i|\leq 2\times 10^ 6$。
| 子任務（測資） | 額外限制 | 分數 |
| 1 (0~4) | $N,M\leq 10^ 4$ | 18 |
| 2 (0~9) | $N,M\leq 3\times 10^ 4$ | 19 |
| 3 (0~14) | $N,M\leq 10^ 5$ | 19 |
| 4 (0~19) | $N,M\leq 3\times 10^ 5$ | 21 |
| 5 (0~25) | $N,M\leq 10^ 6$ | 23 |
Output Format
本題沒有輸出，如果你輸出了任何東西，你將會獲得一個WA。
Sample Input 1
注意：本題沒有輸入，本輸入為提供測試標頭檔（參見Hints）使用。
2 2
-7 3 1
7 -3 1
2 2
-7 3 1
7 -3 1
Sample Output 1
注意：本題沒有輸出，本輸出為提供測試標頭檔（參見Hints）使用。
-49 42 -9 0 1
-49 42 -9 0 1
Hints
這裡有一個測試用的標頭檔，可以用來測試。
該標頭檔接受以下輸入，數字間皆以空白分隔：
第一行：$N, M$；
第二行：$a_0, a_1,\cdots ,a_N$；
第三行：$b_0, b_1,\cdots ,b_M$；
測試程式將會呼叫函數後輸出ans陣列的內容。
Problem Source
Problem set by Yihda Yol
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0~4 | 18 |
| 2 | 0~9 | 19 |
| 3 | 0~14 | 19 |
| 4 | 0~19 | 21 |
| 5 | 0~25 | 23 |