广义斐波那契数列

题解

解

矩阵乘法满足结合律，不满足交换律
$a_3 = Qa_1 * Pa_2$
将$a_1, a_2$ 看做矩阵 $A = (a_1, a_2)$
将$a_2, a_3$ 看做矩阵 $B = (a_2, a_3)$
考虑构造矩阵 $T$, 使得 $A * T = B$

$$\left( \begin{matrix} a_1 & a_2\\ \end{matrix} \right) * \left( \begin{matrix} d & e\\ f & g\\ \end{matrix} \right) = \left( \begin{matrix} a_2 & a_3\\ \end{matrix} \right)$$
显然
$$T = \left( \begin{matrix} 0 & Q\\ 1 & P\\ \end{matrix} \right)$$
所以 $Ans = A * T ^ {n - 2}$
$Answer = Ans_{1,2}$

Code

#include <bits/stdc++.h>
const int N = 5;
#define LL long long
LL P, Q, a1, a2, n, Mod;
struct Node {
    LL m[N][N];
    Node() {memset(m,0,sizeof m);}
    void Clear() {for(int i = 1; i <= 2; i ++) m[i][i] = 1;}
};
Node operator * (const Node a, const Node b) {
    Node ret;
    for(int i = 1; i <= 2; i ++)
        for(int j = 1; j <= 2; j ++)
            for(int k = 1; k <= 2; k ++)
                ret.m[i][j] = (ret.m[i][j] + (a.m[i][k] * b.m[k][j]) % Mod) % Mod;
    return ret;
}
Node Ksm(Node a, int p){
    Node ret; ret.Clear();
    while(p) {
        if(p & 1) ret = ret * a;
        a = a * a;
        p >>= 1;
    }
    return ret;
}
int main() {
    std:: cin >> P >> Q >> a1 >> a2 >> n >> Mod;
    P %= Mod, Q %= Mod, a1 %= Mod, a2 %= Mod;
    Node A;
    A.m[1][2] = Q, A.m[2][1] = 1, A.m[2][2] = P;
    Node Ans = Ksm(A, n - 2);
    Node B; B.m[1][1] = a1, B.m[1][2] = a2;
    Ans = B * Ans;
    std:: cout << Ans.m[1][2] % Mod;
    return 0;
}