P1962 斐波那契数列

洛咕原题

直接把乘号和快速幂重载了。注意该开long long的别忘了开

使用矩乘加速，构造初始矩阵的方法： point_here

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
struct matrix{
    ll a[3][3];
    matrix(){memset(a,0,sizeof(a));}
    matrix operator * (matrix &tmp){
        matrix c;
        for(int i=1;i<=2;++i)
            for(int j=1;j<=2;++j)
                for(int k=1;k<=2;++k)
                    c.a[i][j]=(c.a[i][j]+a[i][k]*tmp.a[k][j]%mod)%mod;
        return c;
    }
    matrix ksm(matrix x,ll y){
        matrix ans;
        ans.a[1][1]=ans.a[2][2]=1;
        for(;y;y>>=1){
            if(y&1) ans=ans*x;
            x=x*x;
        }
        return ans;
    }
}p,st;

int main()
{
    ll n; scanf("%lld",&n); //n也要long long
    p.a[1][2]=p.a[2][1]=p.a[2][2]=1;//构建初始矩阵
    p=p.ksm(p,n+1);
    printf("%lld",p.a[1][1]);
    return 0;
}