두 정수 수열 \(P = (P_0, P_1, \dots, P_{n-1})\) 와 \(Q = (Q_0, Q_1, \dots, Q_{m-1})\) 가 주어진다. 이 둘의 합성곱(convolution) \(C\) 를 구하라. \(C\)는 길이 \(n + m - 1\)의 수열로 다음과 같이 정의된다.

$$ C_k = \sum_{i + j = k} P_i \cdot Q_j \qquad (0 \le k \le n + m - 2) $$

각 \(C_k\)를 \(10^9 + 7\) 로 나눈 나머지로 출력한다.

수열의 길이가 최대 \(6 \times 10^4\)이고 계수가 크므로, 단순한 이중 반복문 \(O(nm)\) 으로는 제한 시간을 통과할 수 없다. 또한 나눗셈의 법 \(10^9 + 7\) 은 통상적인 빠른 합성곱에 바로 쓰기에는 적합하지 않은 형태이므로 주의가 필요하다.

\(1 \le n, m \le 6 \times 10^4\)

\(0 \le P_i, Q_j \le 10^9\)

첫 줄에 두 정수 \(n\)과 \(m\)이 주어진다.

둘째 줄에 \(n\)개의 정수 \(P_0, \dots, P_{n-1}\) 이 주어진다.

셋째 줄에 \(m\)개의 정수 \(Q_0, \dots, Q_{m-1}\) 이 주어진다.

한 줄에 \(n + m - 1\)개의 정수 \(C_0, C_1, \dots, C_{n+m-2}\) 를 공백으로 구분하여 출력한다. 각 값은 \(10^9 + 7\) 로 나눈 나머지이다.

riseoj 작성

출처 Original