CSES - Signal Processing | Xử lí tín hiệu

Tác giả:

Dạng bài

Điểm: 2000 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Cho hai dãy số nguyên \(a\) và \(b\). Tính các giá trị tại mỗi vị trí khi di chuyển dãy \(b\) từ trái sang phải. Giá trị tại mỗi vị trí là tổng của tích các phần tử chồng nhau của dãy \(a\) và \(b\)

Input

Dòng đầu tiên bao gồm hai số nguyên \(n\) và \(m\): độ dài của dãy \(a\) và dãy \(b\).
Dòng tiếp theo gồm \(n\) số nguyên \(a_1, a_2,…,a_n\) là các phần tử của dãy \(a\)
Dòng tiếp theo gồm \(m\) số nguyên \(b_1, b_2,…,b_n\) là các phần tử của dãy \(b\)

Output

In ra \(n + m − 1\) số nguyên: giá trị tại mỗi vị trí từ trái sang phải.

Constraints

\(1\leq n, m \leq 2 ⋅ 10^5\)
\(1\leq a_i, b_i \leq 100\)

Example

Sample input

5 3  
1 3 2 1 4  
1 2 3

Sample output

3 11 13 10 16 9 4

Note

Giải thích:
Tại vị trí thứ 2, vị trí của mảng \(a\) và \(b\) là:
```
1 3 2 1 4
1 2 3
```
Do đó, giá trị tại vị trí thứ 2 là \(2 ⋅ 1 + 3 ⋅ 3 = 11\)

Bình luận

-2

include <bits/stdc++.h>

using namespace std;
typedef double ld;
typedef complex<ld> cd;
const int maxN = 2e5+5;
const int SIZE = 1<<19;
const ld PI = acos(-1);

int N, M;
vector<cd> A(SIZE), B(SIZE);

void fft(vector<cd> &a, bool inv){
int n = (int) a.size();

for(int i = 1, j = 0; i < n; i++){
    int bit = n>>1;
    for(; j&bit; bit >>= 1)
        j ^= bit;
    j ^= bit;

    if(i < j)
        swap(a[i], a[j]);
}

for(int len = 2; len <= n; len <<= 1){
    ld theta = 2*PI / len * (inv ? -1 : 1);
    cd wlen(cos(theta), sin(theta));
    for(int i = 0; i < n; i += len){
        cd w(1);
        for(int j = 0; j < len / 2; j++){
            cd u = a[i+j], v = a[i+j+len/2] * w;
            a[i+j] = u + v;
            a[i+j+len/2] = u - v;
            w *= wlen;
        }
    }
}

if(inv)
    for(cd &z : a)
        z /= n;

}

int main(){
scanf("%d %d", &N, &M);
for(int i = 0, a; i < N; i++){
scanf("%d", &a);
A[i] = a;
}
for(int i = 0, b; i < M; i++){
scanf("%d", &b);
B[M-i-1] = b;
}

fft(A, false);
fft(B, false);
for(int i = 0; i < SIZE; i++)
    A[i] *= B[i];
fft(A, true);

for(int i = 0; i < N+M-1; i++)
    printf("%lld%c", llround(A[i].real()), (" \n")[i==N+M-2]);

}