UVA 10655 Contemplation! Algebra：矩陣快速冪求 a^n + b^n

問題描述

已知 p = a+b，q = ab，求 a^n + b^n。輸入多組 p,q,n，以 0 0 結束。結果保證 64 位有符號整數範圍內。

解題思路

設 f_n = a^n + b^n。易得 f_0 = 2, f_1 = p。遞推：f_n = p * f_{n-1} - q * f_{n-2}。證明：a^n+b^n = (a+b)(a^{n-1}+b^{n-1}) - ab(a^{n-2}+b^{n-2})。構造矩陣：[f_n, f_{n-1}]^T = M * [f_{n-1}, f_{n-2}]^T，其中 M = [[p, -q], [1, 0]]。則 [f_n, f_{n-1}]^T = M^{n-1} * [p, 2]^T。用矩陣快速冂 O(log n) 計算。

代碼實現 (C++)

#include 
using namespace std;
using LL = long long;
struct Mat { LL a[2][2]; };
Mat mul(Mat x, Mat y) {
    Mat r; memset(r.a, 0, sizeof(r.a));
    for (int i = 0; i < 2; ++i)
        for (int k = 0; k < 2; ++k)
            for (int j = 0; j < 2; ++j)
                r.a[i][j] += x.a[i][k] * y.a[k][j];
    return r;
}
Mat mpow(Mat base, LL exp) {
    Mat res; memset(res.a, 0, sizeof(res.a));
    res.a[0][0] = res.a[1][1] = 1;
    while (exp) {
        if (exp & 1) res = mul(res, base);
        base = mul(base, base);
        exp >>= 1;
    }
    return res;
}
int main() {
    LL p, q, n;
    while (cin >> p >> q >> n) {
        if (p == 0 && q == 0) break;
        if (n == 0) { cout << 2 << endl; continue; }
        if (n == 1) { cout << p << endl; continue; }
        Mat M; M.a[0][0]=p; M.a[0][1]=-q; M.a[1][0]=1; M.a[1][1]=0;
        Mat R = mpow(M, n-1);
        LL ans = R.a[0][0] * p + R.a[0][1] * 2;
        cout << ans << endl;
    }
    return 0;
}

複雜度分析

• 時間複雜度：O(log n) 矩陣乘法常數次。
• 空間複雜度：O(1)。

總結

利用二次遞推特徵多項式構造矩陣，快速冂求通項。注意 n=0,1 邊界情況單獨處理。長整型防止中間溢出（題目保證最終結果 64 位內）。