POJ 2601 Simple calculations：線性遞推求解 a₁

POJ 2601 Simple calculations：線性遞推求解 a₁

已知 a₀, a_{n+1} 和 c₁..cₙ，滿足 aᵢ = (a_{i-1} + a_{i+1})/2 - cᵢ (i=1..n)。求 a₁。

數學推導

遞推關係：

a₀ + a₂ - 2a₁ - 2c₁ = 0
a₁ + a₃ - 2a₂ - 2c₂ = 0
...
a_{n-1} + a_{n+1} - 2a_n - 2c_n = 0

累加所有式子，大部分項抵消：

a₀ + a_{n+1} - a₁ - a_n - 2Σcᵢ = 0

繼續利用倒數第二式消去 a_n，最終得到：

n*a₀ + a_{n+1} - (n+1)*a₁ - 2Σ(i=1..n) (n-i+1)*cᵢ = 0

解得：

a₁ = [n*a₀ + a_{n+1} - 2*Σ(n-i+1)*cᵢ] / (n+1)

完整代碼

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    while (cin >> n) {
        double a0, an1;
        cin >> a0 >> an1;
        vector c(n+1);
        for (int i = 1; i <= n; ++i) cin >> c[i];
        
        double sum = 0;
        for (int i = 1; i <= n; ++i) {
            sum += 2 * (n - i + 1) * c[i];
        }
        
        double a1 = (n * a0 + an1 - sum) / (n + 1);
        cout << fixed << setprecision(2) << a1 << "\n";
    }
    return 0;
}

樣例驗證

Input:
1
50.50
25.50
10.15

n=1: a₁ = (1*50.50 + 25.50 - 2*1*10.15) / 2
    = (76 - 20.30) / 2 = 55.70 / 2 = 27.85 ✓

關鍵點

• 數學推導消去中間變量，直接求 a₁
• 雙精度足夠，輸出保留 2 位小數
• 公式對稱優美，體現線性遞推的代數結構

複雜度

• 時間：O(n)
• 空間：O(n) 或 O(1) 邊讀邊累加
• n ≤ 3000，極快

此題是線性遞推方程組求解的代數技巧展示，避免了高斯消元 O(n³)，利用疊加抵消直接得出封閉公式。