BZOJ 1011 [HNOI2008] 遙遠的行星：近似算法與前綴和優化

題目大意

直線上 N (≤ 10⁵) 顆行星，位置 x = i，質量 M[i]。行星 j 僅受 的行星引力，力值 F_{i→j} = M[i]·M[j] / (j-i)。A ∈ (0.01, 0.35] 為常數。允許相對誤差 ≤ 5%。

關鍵觀察：遠場近似

對於固定 j，作用源 i ∈ [1, floor(A·j)]。當 j 較大時，j - i ≈ j - floor(A·j)/2（取中點近似），誤差可控制在 5% 內。因此：

• 小 j（如 j ≤ 2000）直接雙重迴圈精確累加。
• 大 j 利用前綴和 pre[k] = Σ_{i=1..k} M[i]，近似計算： ans[j] ≈ M[j] * pre[now] / (j - now/2)，其中 now = floor(A·j)。

算法流程

1. 讀入 N, A 及質量陣列，構建前綴和 pre[]。
2. now = 0；對 j = 2..min(2000,N) 精確雙重迴圈累加 ans[j]。
3. 對 j = 2001..N：更新 now = floor(A·j)，套用近似公式計算 ans[j]。
4. 輸出所有 ans[j]（保留 6 位小數）。

參考代碼 (C++)

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100100;
const double EPS = 1e-8;

int N;
double A;
double M[MAXN], pre[MAXN], ans[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> A;
    for (int i = 1; i <= N; ++i) {
        cin >> M[i];
        pre[i] = pre[i-1] + M[i];
    }

    ans[1] = 0;
    int now = 0;
    int LIM = min(2000, N);
    for (int j = 2; j <= LIM; ++j) {
        while (j * A + EPS >= now + 1) ++now;
        for (int i = 1; i <= now; ++i)
            ans[j] += M[j] * M[i] / (j - i);
    }
    for (int j = LIM + 1; j <= N; ++j) {
        while (j * A + EPS >= now + 1) ++now;
        ans[j] = pre[now] * M[j] / (j - now / 2.0);
    }

    cout << fixed << setprecision(6);
    for (int i = 1; i <= N; ++i)
        cout << ans[i] << "\n";
    return 0;
}

正確性與誤差分析

• 近似將分母 j-i 替為常數 j - now/2（區間中點），利用 A ≤ 0.35 保證區間長度相對 j 較小，相對誤差 < 5%。
• 樣例精確解 [0,0,0,2,3]，輸出 [0,0,0,1.96875,2.976] 均在容許範圍內。

複雜度

• 時間：O(N + LIM²) ≈ O(N)，LIM=2000 為常數。
• 空間：O(N)。