Fast Fourier Transform (FFT)

题面

实现复数一维信号的 FFT（O(N log N)）：输入/输出为交错实部/虚部 [re0, im0, re1, im1, ...]，结果写入 spectrum。

Implementation Requirements

• External libraries (cuFFT etc.) are not permitted
• The solve function signature must remain unchanged
• 计算在 GPU 端完成，host 侧不可调用 FFT
• 输入输出均为交错复数布局

Examples

见页面 N=4、N=2 的示例。

Constraints

• 1 ≤ N ≤ 262,144；float32；绝对/相对误差 ≤ 1e‑3
• 输入输出数组长度均为 2×N；Performance: N = 262,144