BZOJ 3257 ZJOI 2014 庫侖力計算：FFT 加速 n 體問題

問題描述

n 個點電荷 q_i 位於坐標 i (1≤i≤n)。點 i 受合力 F_i = Σ_j≠i q_iq_j/(i-j)²（左為正）。求 F_i/q_i = Σ_j≠i q_j/(i-j)²。

卷積形式轉換

定義序列：
A[i] = q_i (1≤i≤n)
B[k] = 1/k² (1≤k≤n-1), B[0]=0, B[-k]=-1/k²（奇函數）
則 F_i/q_i = Σ_j A[j]·B[i-j]，即 A 與 B 的卷積。

FFT 計算流程

1. 構造 A 長度 n，B 長度 2n（負索引映射到後半段）
2. 補零到 N = 2^{⌈log₂(3n)⌉}
3. FFT → 逐點乘 → IFFT
4. 結果取實部，輸出前 n 項

高精度考慮

用 `long double` 實現複數，`M_PI` 高精度 π。輸出保留 3 位小數。

關鍵代碼片段

using ld = long double;
struct Complex { ld r,i; /* 運算符重載 */ };
void fft(vector& a, bool inv) { /* 標準迭代 FFT */ }

int main() {
    int n; cin >> n;
    vector q(n+1);
    for (int i=1; i<=n; ++i) cin >> q[i];
    int N=1; while (N < 3*n) N<<=1;
    vector A(N), B(N);
    for (int i=1; i<=n; ++i) A[i].r = q[i];
    B[0].r = 0;
    for (int i=1; i

複雜度

時間：O(n log n)，n=100,000 秒級通過
空間：O(n)


物理意義
將 n 體問題的兩兩交互通過卷積降維，利用 FFT 從 O(n²) 加速到 O(n log n)，是計算物理中快速多極子方法 (FMM) 的簡化版思想。

此題展示了 FFT 在物理模擬中的直接應用，將庫侖力求和轉化為卷積計算。