P1349广义斐波那契数列---矩阵快速幂解析

做此题之前，我们不妨先做做正常的斐波那契数列

P1962

f(n)=f(n-1)+f(n-2)

既p=1,q=1,a1=1,a2=1;

写出前几项:

1 1 2 3 5 8 11 19...

{{1,1}}*{{1,1},{1,0}}={{2,1}}

{{2,1}}*{{1,1},{1,0}}={{3,2}}

{{3,2}}*{{1,1},{1,0}}={{5,3}}

....

比如

{{第n项,第n-1项}}*{{1,1},{1,0}}={{第n+1项,第n项}}

为什么是{{1,1},{1,0}}前面两个1是系数f(n-1),f(n-2)

后面两个可以带值计算出来

(证明略)

如果令{{1,1},{1,0}}=G

因此,求斐波那契数列第n项

{{f(n),f()n-1}}={{f(1),f(0)}}*G^(n-1)

或者

{{f(n),f()n-1}}={{f(2),f(1)}}*G^(n-2)

所以 算出G^ 再乘以 {f(1),f(0)}即可

P1962AC代码

#include <iostream>
#include <vector>
#define int long long
using namespace std;
int n;
const int mod = 1e9 + 7;
// 矩阵相乘
// a的列数一定要等于b的行数
vector<vector<int>> multiply(vector<vector<int>>& a, vector<vector<int>>& b) {
    int n = a.size();
    int m = b[0].size();
    int k = a[0].size();
    vector<vector<int>> ans(n, vector<int>(m, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            for (int c = 0; c < k; c++) {
                ans[i][j] += (a[i][c]%mod * b[c][j]%mod)%mod;
                ans[i][j] %= mod;
            }
        }
    }
    return ans;
}

// 矩阵快速幂
vector<vector<int>> power(vector<vector<int>>& m, int p) {
    int n = m.size();
    vector<vector<int>> ans(n, vector<int>(n, 0));
    for (int i = 0; i < n; i++) {
        ans[i][i] = 1;
    }
    for (; p != 0; p >>= 1) {
        if ((p & 1) != 0) {
            ans = multiply(ans, m);
        }
        m = multiply(m, m);
    }
    return ans;
}

int fib(int n) {
    if (n == 0) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    vector<vector<int>> start = { { 1, 0 } };
    vector<vector<int>> base = {
        { 1, 1 },
        { 1, 0 }
    };
    vector<vector<int>> temp = power(base, n - 1);
    vector<vector<int>> ans = multiply(start, temp);
    return ans[0][0];
}

signed main() {
    cin >> n;
    cout<<fib(n);
    return 0;
}

下面会到P1349 广义斐波那契

f(n)=Af(n-1)+Bf(n-2)

可以明确的告诉你

G={{A,1},{B,0}};

所以在此递推式 对于任一项n

有

{{f(n),f(n-1)}}={{f(2),f(1)}}*G^(n-2)

#include <iostream>
#include <vector>
#define int long long
using namespace std;
int p, q, a1, a2, nn, mod;
// 矩阵相乘
// a的列数一定要等于b的行数
vector<vector<int>> start;
vector<vector<int>> base;
vector<vector<int>> multiply(vector<vector<int>>& a, vector<vector<int>>& b) {
    int n = a.size();
    int m = b[0].size();
    int k = a[0].size();
    vector<vector<int>> ans(n, vector<int>(m, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            for (int c = 0; c < k; c++) {
                ans[i][j] += (a[i][c] % mod * b[c][j] % mod) % mod;
                ans[i][j] %= mod;
            }
        }
    }
    return ans;
}

// 矩阵快速幂
vector<vector<int>> power(vector<vector<int>>& m, int p) {
    int n = m.size();
    vector<vector<int>> ans(n, vector<int>(n, 0));
    for (int i = 0; i < n; i++) {
        ans[i][i] = 1;
    }
    for (; p != 0; p >>= 1) {
        if ((p & 1) != 0) {
            ans = multiply(ans, m);
        }
        m = multiply(m, m);
    }
    return ans;
}

int fib(int n) {
    if (n == 1)return a1;
    if (n == 2)return a2;
    vector<vector<int>> temp = power(base, n - 2);
    vector<vector<int>> ans = multiply(start, temp);
    return ans[0][0];
}

signed main() {
    cin >> p >> q >> a1 >> a2 >> nn >> mod;
    start = { {a2,a1} };
    base = {
        {p,1},
        {q,0}
    };
    cout << fib(nn);
    return 0;
}