【UVA-10655】Contemplation! Algebra【矩阵快速幂】

【UVA-10655】Contemplation! Algebra【矩阵快速幂】

问题链接:https://vjudge.net/problem/UVA-10655

Solution:

在纸上尝试一下,发现:

\((a + b)(a + b) – 2ab = a^2 + b^2\)

\((a^2 + b^2)(a + b) – (a + b)ab = a^3 + b^3\)

\((a^3 + b^3)(a + b) – (a^2 + b^2)ab = a^4 + b^4\)

……

转移方式是固定的,我们可以写出矩阵变换式:

\((^{a^n + b^n}_{a^{n – 1} + b^{n – 1}}) = (^{a + b}_1\)      \(^{-ab}_0) ^{n – 1}(^{a + b}_{2})\)

根据这个写矩阵快速幂就好。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

typedef long long LL;
const int LIM = 2;
struct Matrix {
    LL v[LIM][LIM];
    Matrix operator * (const Matrix & m) const {
        Matrix ret = {0};
        for (int i = 0; i < LIM; i++) {
            for (int k = 0; k < LIM; k++) {
                if (v[i][k])
                    for (int j = 0; j < LIM; j++) {
                        ret.v[i][j] = (ret.v[i][j] + v[i][k] * m.v[k][j]);
                    }
            }
        }
        return ret;
    }
};
// p = a + b, q = ab
LL p, q, n;
Matrix base;

void build() {
    base.v[0][0] = p;
    base.v[0][1] = -q;
    base.v[1][0] = 1;
    base.v[1][1] = 0;
}

Matrix fastPow(LL p, Matrix m) {
    Matrix ret = {0};
    for(int i = 0; i < LIM; i++) ret.v[i][i] = 1;
    while (p) {
        if (p & 1) ret = ret * m;
        if (p) m = m * m;
        p >>= 1;
    }
    return ret;
}

int main() {
    while (scanf("%lld%lld%lld", &p, &q, &n) == 3 && (p || q || n)) {
        if (n == 0) printf("2\n");
        else if (n == 1) printf("%lld\n", p);
        else {
            build();
            Matrix trans = fastPow(n - 1, base);
            printf("%lld\n", trans.v[0][0] * p + trans.v[0][1] * 2);
        }
    }
    return 0;
}