Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Toán cho CNTT] Tích chập vòng qua DFT

    Tích chập tuần hoàn (Circular convolution) qua DFT

    Định lý tích chập: tích chập vòng của hai dãy tương ứng với nhân từng điểm trong miền tần số:

    c=IDFT(DFT(a)⋅DFT(b)),c[m]=∑t=0n−1a[t] b[(m−t) mod n]c = \text{IDFT}\big(\text{DFT}(a)\cdot \text{DFT}(b)\big), \qquad c[m] = \sum_{t=0}^{n-1} a[t]\, b[(m-t)\bmod n]c=IDFT(DFT(a)⋅DFT(b)),c[m]=∑t=0n−1​a[t]b[(m−t)modn]

    Kết quả là số nguyên (đầu vào nguyên) nên hãy làm tròn về số nguyên gần nhất.

    Ví dụ

    a=[1,2,3]a = [1,2,3]a=[1,2,3], b=[1,1,1]b = [1,1,1]b=[1,1,1] cho c=[6,6,6]c = [6,6,6]c=[6,6,6] (mỗi phần tử là tổng của aaa).

    • Định dạng đầu vào:

      Dòng 1: nnn. Dòng 2: nnn số nguyên aaa. Dòng 3: nnn số nguyên bbb.

    • Ràng buộc đầu vào:

      1≤n≤641 \le n \le 641≤n≤64; ∣a[t]∣,∣b[t]∣≤100|a[t]|, |b[t]| \le 100∣a[t]∣,∣b[t]∣≤100.

    • Định dạng đầu ra:

      Một dòng gồm nnn số c[0..n−1]c[0..n-1]c[0..n−1], cách nhau dấu cách, định dạng 4 chữ số thập phân.

    Ví dụ:

    Đầu vào:

    3
1 2 3
1 1 1

    Đầu ra:

    6.0000 6.0000 6.0000

    Giải thích:

    Tich chap vong voi day toan 1 cho moi phan tu = tong a = 6.

    Đang tải editor...