Fibonacci ### 第 n 项

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1204 字

输入n,m，求Fibonacci第n项F_n

一本通
例

正文

/*
原题：T1642「一本通 6.5 例 2」Fibonacci 第 n 项
题意：输入 n,m，求 Fibonacci 第 n 项 F_n 对 m 取模的值，其中 F_0=0,F_1=1。
思路：取转移矩阵 M=[[1,1],[1,0]]，则 M^k=[[F_{k+1},F_k],[F_k,F_{k-1}]]。
用矩阵快速幂求 M^n，其左下角（或右上角）元素即为 F_n。
复杂度：时间 O(log n)，空间 O(1)
易错点：1) 矩阵乘法中每一项都要先取模再累加，防止中间结果溢出 long long；
2) 快速幂的初值必须是单位矩阵而不是全零矩阵；
3) n=0 时得到单位矩阵，左下角为 0，结果正确，无需特判。
*/
#include <bits/stdc++.h>
using namespace std;
struct Mat{
    long long v[2][2];
};
Mat mul(const Mat& x,const Mat& y,long long mod){
    Mat r;
    memset(r.v,0,sizeof(r.v));
    for(int i=0;i<2;i++){
        for(int k=0;k<2;k++){
            for(int j=0;j<2;j++){
                r.v[i][j]=(r.v[i][j]+x.v[i][k]*y.v[k][j])%mod;
            }
        }
    }
    return r;
}
Mat mpow(Mat a,long long n,long long mod){
    Mat r;
    memset(r.v,0,sizeof(r.v));
    r.v[0][0]=1;
    r.v[1][1]=1;
    while(n>0){
        if(n&1){
            r=mul(r,a,mod);
        }
        a=mul(a,a,mod);
        n>>=1;
    }
    return r;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    long long n,m;
    cin>>n>>m;
    Mat base;
    base.v[0][0]=1;
    base.v[0][1]=1;
    base.v[1][0]=1;
    base.v[1][1]=0;
    Mat r=mpow(base,n,m);
    cout<<r.v[1][0]<<"\n";
    return 0;
}

Fibonacci ### 第 n 项

正文

一本通·提高篇的其它内容