-矩阵运算-递推- [洛谷 P1349]广义斐波那契数列

题目描述

广义的斐波那契数列是指形如 $an=p \times a{n-1} + q \times a_{n-2}$ 的数列。今给定数列的两系数 $p$ 和 $q$ ，以及数列的最前两项 $a_1$ 和 $a_2$ ，另给出两个整数 $n$ 和 $m$ ，试求数列的第 $n$ 项除以 $m$ 的余数。

输入格式

输入包含一行6个整数。依次是 $p,q,a_1,a_2$ ，其中在 $p,q,a_1,a_2$ 整数范围内， $n$ 和 $m$ 在长整数范围内。

输出格式

输出包含一行一个整数，即$a_n$除以$m$的余数。

输入样例

1 1 1 1 10 7

输出样例

6

说明

数列第10项是55，除以7的余数为6。

Solution

最近刚学了矩阵快速幂，便想找几道题练练手。

这道题其实就是斐波那契的变种（好像是句废话），所以我们只需要将那个式子改一改就可以了。

而且我个人比较喜欢重载运算符。

注意：千万不要把 $p$ 和 $q$ 写反！

还有，要开long long。

Code

#include <iostream>
#include <iostream>
#include <cstdio>
#include <cstring>
#define ll long long
ll n , m , p , q , a_1 , a_2;
struct Mat{
    ll a[2][2];
    void clear() {
        memset(a , 0 , sizeof(a));
    }
    void init() {
        memset(a , 0 , sizeof(a));
        for (int i = 0 ; i <= 1 ; i++) {
            a[i][i] = 1;
        }
    }
};
ll mula(ll x , ll y) {
    x += y;
    if (x >= m) x -= m;
    return x;
}
ll mult(ll x , ll y) {
    ll p = 0;
    while (y) {
        if (y & 1) p = (p + x) % m;
        x = (x + x) % m;
        y >>= 1;
    }
    return p;
}
Mat operator * (Mat a , Mat b) {
    Mat c;
    c.clear();
    for (int i = 0 ; i < 2 ; i++) {
        for (int j = 0 ; j < 2 ; j++) {
            for (int k = 0 ; k < 2 ; k++) {
                c.a[i][j] = mula(c.a[i][j] %m , mult(a.a[i][k] , b.a[k][j]) % m) % m;
            }
        }
    }
    return c;
}
Mat qpow(Mat a , ll n) {
    Mat b;
    b.init();
    while (n) {
        if (n & 1) b = b * a;
        n >>= 1;
        a = a * a;
    }
    return b;
}
int main() {
    scanf("%lld%lld%lld%lld%lld%lld" , &q , &p , &a_1 , &a_2 , &n , &m);
    Mat f , a , w;
    f.clear();
    a.clear();
    w.clear();
    f.a[0][0] = a_1;
    f.a[0][1] = a_2;
    a.a[0][0] = 0;
    a.a[1][0] = 1;
    a.a[0][1] = p;
    a.a[1][1] = q;
    w = f * qpow(a , n - 2);
    std::cout << w.a[0][1] % m;
}