【UVA-10518】How Many Calls?【矩阵快速幂】

【UVA-10518】How Many Calls?【矩阵快速幂】

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

Solution:

题目说,这道题我们不关心Fibonacci数列,实际上。。它还是个类似的斐波那契数列,只不过有变化,我们使用\(F_n\)来表示新数列的第n项,经过分析,有:

\(F_0 = 1\),

\(F_1 = 1\),

\(F_n = F_{n – 1} + F_{n – 2} + 1\).

根据这个来写矩阵快速幂就好,复杂度\(O(3^3logn)\)。

另外,关于输入结束,虽然题目说n和m都是0的时候结束,但是我们根据这两个值发现,在合法情况下,n可能是0,而m不能为0,那么判断结束只要判断m是不是0就可以,不用管n。

#include <iostream>

using namespace std;

typedef unsigned long long ULL;
ULL n, m;

const int LIM = 3;
struct Matrix {
    ULL 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]) % ::m;
        return ret;
    }
};

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

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    Matrix base = {1, 1, 1, 1, 0, 0, 0, 0, 1};
    for (int k = 1; cin >> n >> m && m; k++) {
        cout << "Case " << k << ": " << n << " " << m << " ";
        if (n) cout << fastPow(n, base) % m << "\n";
        else cout << 1 % m << "\n";
    }
    return 0;
}