Tương Quan Chéo Hai Dãy Số

Buổi 60 — FFT / NTT
Points
30
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
number
Submissions
Đề bài

Cho hai dãy số nguyên $A_0, A_1, \dots, A_{N-1}$ và $B_0, B_1, \dots, B_{N-1}$. Với mỗi độ lệch $k \in [-(N-1), N-1]$, hãy tính: \[C_k = \sum_{\substack{0 \le i, j < N \\ i - j = k}} A_i \cdot B_j\]

Dữ liệu vào
  • Dòng đầu chứa số nguyên $N$ ($1 \le N \le 10^5$).
  • Dòng thứ hai chứa $N$ số nguyên $A_0, \dots, A_{N-1}$ ($|A_i| \le 1000$).
  • Dòng thứ ba chứa $N$ số nguyên $B_0, \dots, B_{N-1}$ ($|B_j| \le 1000$).
Dữ liệu ra

In ra $2N - 1$ số nguyên lần lượt là $C_{-(N-1)}, C_{-(N-2)}, \dots, C_{N-1}$ cách nhau bởi dấu cách.

Ví dụ
Input Output
3
1 2 3
4 5 6
6 17 32 23 12
1
5
-3
-15
Giới hạn
  • $1 \le N \le 10^5$
  • $|A_i|, |B_j| \le 1000$
Draft saved