Bài tập | NEU OJ

Cho hai đa thức $A(x) = \sum_{i=0}^{n} a_i x^i$ và $B(x) = \sum_{j=0}^{m} b_j x^j$ với các hệ số nguyên. Hãy tính đa thức tích $C(x) = A(x) \cdot B(x)$ , với mỗi hệ số lấy theo modulo $p$ ( $p$ là số nguyên tố nhỏ).

Hệ số $c_k = \left(\sum_{i+j=k} a_i b_j\right) \bmod p$ .

Ví dụ: $A = 1 + 2x$ , $B = 3 + 4x$ cho $C = 3 + 10x + 8x^2$ .

Định dạng đầu vào:
Dòng đầu chứa $p$ . Dòng thứ hai chứa $n$ rồi $n+1$ hệ số $a_0, \dots, a_n$ . Dòng thứ ba chứa $m$ rồi $m+1$ hệ số $b_0, \dots, b_m$ .
Ràng buộc đầu vào:
$2 \le p \le 10^9+7$ ( $p$ nguyên tố), $0 \le n, m \le 2000$ , $0 \le a_i, b_j < p$ .
Định dạng đầu ra:
In $n+m+1$ hệ số $c_0, \dots, c_{n+m}$ (đã lấy modulo $p$ ) trên một dòng, cách nhau bởi dấu cách.

solution

Đề bài: [Giải thuật] Nhân đa thức modulo