Fibonacci

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

多组数据，每组一个整数n，输出F_nmod1

一本通
练习

正文

/*
原题：T1645「一本通 6.5 练习 1」Fibonacci
题意：多组数据，每组一个整数 n，输出 F_n mod 10000，读入 -1 结束。
思路：同样用 [[1,1],[1,0]] 的矩阵快速幂，每次 O(log n) 求出 F_n 后对 10000 取模。
复杂度：每组 O(log n)，空间 O(1)
易错点：1) 多组数据读到 -1 为止，循环条件里先判 -1 再计算；
2) 输出的是普通整数不要补前导零；
3) 快速幂初值用单位矩阵。
*/
#include <bits/stdc++.h>
using namespace std;
const long long MOD=10000;
struct Mat{
    long long v[2][2];
};
Mat mul(const Mat& x,const Mat& y){
    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){
    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);
        }
        a=mul(a,a);
        n>>=1;
    }
    return r;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    long long n;
    while(cin>>n && n!=-1){
        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);
        cout<<r.v[1][0]<<"\n";
    }
    return 0;
}

Fibonacci

正文

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