TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

50.0% (5/10)

Submission's AC Ratio

39.1% (59/151)

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[]);:傳入非負整數NM分別代表$\deg f$和$\deg g$;ab分別為長度為$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

注意:本題沒有輸入,本輸入為提供測試標頭檔(參見Hints)使用。
2 2
-7 3 1
7 -3 1

Sample Output

注意:本題沒有輸出,本輸出為提供測試標頭檔(參見Hints)使用。
-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

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 5900 262144 262144 1 2 3 4 5
1 5900 262144 262144 1 2 3 4 5
2 5900 262144 262144 1 2 3 4 5
3 5900 262144 262144 1 2 3 4 5
4 5900 262144 262144 1 2 3 4 5
5 5900 262144 262144 2 3 4 5
6 5900 262144 262144 2 3 4 5
7 5900 262144 262144 2 3 4 5
8 5900 262144 262144 2 3 4 5
9 5900 262144 262144 2 3 4 5
10 5900 262144 262144 3 4 5
11 5900 262144 262144 3 4 5
12 5900 262144 262144 3 4 5
13 5900 262144 262144 3 4 5
14 5900 262144 262144 3 4 5
15 5900 262144 262144 4 5
16 5900 262144 262144 4 5
17 5900 262144 262144 4 5
18 5900 262144 262144 4 5
19 5900 262144 262144 4 5
20 5900 262144 262144 5
21 5900 262144 262144 5
22 5900 262144 262144 5
23 5900 262144 262144 5
24 5900 262144 262144 5
25 5900 262144 262144 5