Luogu P1962 斐波那契数列（矩阵乘法模板）

累了明天再解释

做这道题需要一些关于矩阵乘法的基础知识。

1. 矩阵乘法的基础运算

只有当矩阵A的列数等于矩阵B的行数时，A与B可以相乘（A的行数不一定等于B的列数）。

代码实现（重载运算符）：

struct matrix {

    int ma[][];

};

matrix operator * (const matrix &A,const matrix &B) {

    matrix C;

    for(int i = ; i < ; i++)

        for(int j = ; j < ; j++)

            for(int k = ; k < 3; k++)

                C.ma[i][j] = C.ma[i][j] + A.ma[i][k] * B.ma[k][j];

    return C;

}

2. 单位矩阵

主对角线上的元素都为1，其余元素全为0的n阶矩阵称为n阶单位矩阵，记为

或

可以通过模拟推出，任何其他矩阵 * 单位矩阵 = 它本身。

回到这道题：

因为 f[i] = f[i-1] + f[i-2]，首先构造一个矩阵 [ f[i] f[i-1] ]

它应该等于 [ f[i-1] f[i-2] ] * A.

由于f[i] = f[i-1] *1 + f[i-2]*1，所以矩阵A的第一列应该都为1；

f[i-1] = f[i-1] *1 + f[i-2]*0，所以第二列为1和0；

即

得到以下公式

可以看出，求斐波那契数列即为求刚刚推导出的这个矩阵的n次幂；

这时就可以用快速幂来解决这道题了w

void quickpow(int b) {

    while(b) {

        if(b & ) ans = ans * base;

        base = base * base;

        b >>= ;

    }

}

int main() {

    if(n <= ) {

        printf("");

        return ;

    }

    base.a[][] = base.a[][] = base.a[][] = ;

    ans.a[][] = ans.a[][] = ;

    quickpow(n - );

    printf("%d",ans.a[][]);

    return ;

}

（由于fibonacci数列的前两个数字=1已经给出，矩阵(f[2],f[1])即(1,1)是已知的，所以快速幂只要进行n-2次）

求的时候ans矩阵的第一个数即为答案。

一个小优化：当base自乘时，求出的数组刚好为

　　所以只要看n-1次的base[0][0]就可以了qwq（或者n次的base[0][1])

代码如下（我做的时候没有用重载运算符而是写了个函数来实现矩阵乘法的）

#include<cstdio>

#define ll long long

using namespace std;

const ll mod = ;

struct matrix {

    ll ma[][];

};

matrix ans;

ll n;

matrix mul(matrix A,matrix B) {

    matrix C;

    C.ma[][] = C.ma[][] = C.ma[][] = C.ma[][] = ;

    for(int i = ; i < ; i++)

        for(int j = ; j < ; j++)

            for(int k = ; k < ; k++)

                C.ma[i][j] += A.ma[i][k] * B.ma[k][j] % mod;

    return C;

}

matrix quickpow(matrix A,ll n) {

    matrix B;

    B.ma[][] = B.ma[][] = ;

    B.ma[][] = B.ma[][] = ;

    while(n) {

        if(n&)B = mul(A,B);

        A = mul(A,A);

        n >>= ;

    }

    return B;

}

int main() {

    scanf("%lld",&n);

    matrix A;

    A.ma[][] = A.ma[][] = A.ma[][] = ;

    A.ma[][] = ;

    ans = quickpow (A,n);

    printf("%lld",ans.ma[][]%mod);

    return ;

}

巴特西

Luogu P1962 斐波那契数列（矩阵乘法模板）

最新文章

热门文章