[luogu P1962] 斐波那契数列（带快速幂矩阵乘法模板）

题目背景

大家都知道，斐波那契数列是满足如下性质的一个数列：

• f(1) = 1

• f(2) = 1

• f(n) = f(n-1) + f(n-2) (n ≥ 2 且 n 为整数)

题目描述

请你求出 f(n) mod 1000000007 的值。

输入输出格式

输入格式：

·第 1 行：一个整数 n

输出格式：

第 1 行： f(n) mod 1000000007 的值

输入输出样例

输入样例#1：

5

输出样例#1：

5

输入样例#2：

10

输出样例#2：

55

说明

对于 60% 的数据： n ≤ 92

对于 100% 的数据： n在long long(INT64)范围内。

嗯，用这个题来打个矩阵快速幂模板(～￣▽￣)～

code:

//By Menteur_Hxy

#include<cstdio>

#include<iostream>

#include<cstring>

using namespace std;

const long long MOD=1000000007;

const int MAX=3;

const int INF=0x3f3f3f3f;

long long rd() {//一开始写的快读是int的交了三回才发现 o(╥﹏╥)o

    long long x=0;

    int fla=1; char c=' ';

    while(c>'9'|| c<'0') {if(c=='-') fla=-fla; c=getchar();}

    while(c<='9'&&c>='0') x=x*10+c-'0',c=getchar();

    return x*fla;

}

struct mat{ //Matrix 矩阵

    long long da[MAX][MAX];

    int n,m;

    mat(int x=1,int y=1) {

        n=x,m=y;

        memset(da,0,sizeof da);

    }

    void operator =(mat x) {

        n=x.n,m=x.m;

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

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

                da[i][j]=x.da[i][j];

    } 

    mat operator *(mat b) { //注意：需a.m==b.n

        mat c;

        c.n=n;c.m=b.m;

        for(int i=1;i<=c.n;i++)

            for(int j=1;j<=c.m;j++) {

                c.da[i][j]=0;

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

                    c.da[i][j]+=(da[i][k]%MOD*b.da[k][j]%MOD)%MOD,c.da[i][j]%=MOD;

                    // 第一次把b.da[k][j] 打成da[k][j] T^T

            }

        return c;

    }

    void print() {

        for(int i=1;i<=n;i++){

            printf("%d",da[i][1]);

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

                printf(" %d",da[i][j]);

            printf("\n");

        }

    }

    void mrd() {

        n=rd(),m=rd();

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

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

                da[i][j]=rd();

    }

    mat mul(mat b,long long d) {// a乘以b的d次方

        mat c=*this;

        for(;d;d>>=1) {

            if(d&1) c=c*b;

            b=b*b;

        }

        return c;

    }

};

int main() {

    long long num=rd();

    mat a,b;

    a.n=1,a.m=2;

    a.da[1][1]=0,a.da[1][2]=1;

    b.n=b.m=2;

    b.da[1][2]=b.da[2][1]=b.da[2][2]=1;

//  for(long long i=1;i<=x;i++) a=a*b;

//  a.print();

//  for(;num;num>>=1) {

//      if(num&1) a=a*b;

//      b=b*b;

//  }

    a=a.mul(b,num);

    printf("%lld",a.da[1][1]);

    return 0;

}

巴特西

[luogu P1962] 斐波那契数列（带快速幂矩阵乘法模板）

最新文章

热门文章