Fibonacci 前 n 项和

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

输入n,m，求Fibonacci前n项和S_

一本通
例

正文

/*
原题：T1643「一本通 6.5 例 3」Fibonacci 前 n 项和
题意：输入 n,m，求 Fibonacci 前 n 项和 S_n=F_1+...+F_n 对 m 取模的值，F_1=F_2=1。
思路：把和放进状态里，构造三维状态 [F_{k+1},F_k,S_k]。
转移矩阵 M=[[1,1,0],[1,0,0],[1,0,1]] 满足 M·[F_k,F_{k-1},S_{k-1}]^T=[F_{k+1},F_k,S_k]^T。
初始向量 [F_1,F_0,S_0]^T=[1,0,0]^T，故 S_n=(M^n) 第三行与初始向量作积，即取 (M^n)[2][0]。
复杂度：时间 O(log n)，空间 O(1)
易错点：1) 初始向量是 [1,0,0] 而非 [1,1,0]，F_0=0 别写成 1；
2) 每次乘法元素先取模，避免溢出；
3) 快速幂初值为单位矩阵。
*/
#include <bits/stdc++.h>
using namespace std;
struct Mat{
    long long v[3][3];
};
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<3;i++){
        for(int k=0;k<3;k++){
            for(int j=0;j<3;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;
    r.v[2][2]=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;
    memset(base.v,0,sizeof(base.v));
    base.v[0][0]=1;
    base.v[0][1]=1;
    base.v[1][0]=1;
    base.v[2][0]=1;
    base.v[2][1]=0;
    base.v[2][2]=1;
    Mat r=mpow(base,n,m);
    cout<<r.v[2][0]<<"\n";
    return 0;
}

Fibonacci 前 n 项和

正文

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