Loj10222 佳佳的Fibonacci(矩阵乘法)

这里是简介

题面

给定$n,m$,求:

其中$f_i$为斐波那契数列的第$i$项

题解

不妨设:

则可以设:

所以有:

然后就可以用矩阵乘法加速递推了。

#include <cstdio>
#include <cstring>

int n, m;
struct Matrix {
    int a[4][4];
    Matrix() { memset(a, 0, sizeof a); }
    inline int* operator [] (const int &x) { return a[x]; }
    inline Matrix operator * (Matrix &b) const {
        Matrix ret;
        for(int i = 0; i < 4; ++i)
            for(int k = 0; k < 4; ++k)
                for(int j = 0; j < 4; ++j)
                    (ret[i][j] += 1ll * a[i][k] * b[k][j] % m) %= m;
        return ret;
    }
} S, T;

int main () {
    scanf("%d%d", &n, &m); int k = n;
    S[0][1] = 1;
    T[0][0] = T[0][1] = T[0][2] = 1;
    T[1][0] = T[1][2] = 1;
    T[2][2] = T[2][3] = 1;
    T[3][3] = 1;
    while(k) {
        if(k & 1) S = S * T;
        T = T * T, k >>= 1;
    }
    printf("%lld\n", (1ll * n * S[0][2] % m + m - S[0][3]) % m);
    return 0;
}