蓝桥杯 研究兔子的土豪（疯狂雇主） 矩阵快速幂

问题描述

　　如果你还没有看过研究兔子的土豪，那么请你先去看那道题。
　　HWD老师研究兔子时的某天，他突然不幸的发作了他的密集恐惧症，于是只能放了他的所有兔子……然后，他还是想去研究兔子，于是捡回了他那个伟大的笼子，又买了许多兔子……他依旧开始研究，发现这两批兔子的繁衍规律完全相同……他就这么让兔子繁衍着，直到某天，他怕他的密集恐惧症重新发作，于是，他又找到了那个雇主，但这个雇主的强迫症加重了，他只每次收购10^9+7只兔子，HWD老师再次尽量多的卖出了他已久的兔子，再次数着剩下陪伴他的它们……
　　后来，HWD老师知道了两次收购他兔子的那个人其实叫LZH……

输入格式

　　HWD老师让兔子繁衍了几代（一个整数，没有其他字符）。

输出格式

　　HWD老师剩余（残余？）的兔子（一个整数，忽略行尾回车及空格）。

样例输入

1

样例输出

1

数据规模和约定

　　兔子的总量最大时小于HWD老师笼子的大小。
　　f[1]=1，f[2]=1，f[3]=2 ……

这又是一件悲伤的故事。

这是这道题https://www.cnblogs.com/fx1998/p/12712789.html的数据强化版，需要再配合矩阵快速幂。

然后然后在把以前的矩阵快速幂模板拿过来改了改发现又出错了，然后然后又从头复习了一遍矩阵快速幂，然后然后一点一点的debug。

然后然后发现又又又是取模的细节操作错了。

得出结论：矩阵快速幂还是不熟练。

AC代码

#include <bits/stdc++.h>
using namespace std;
const int p = 1000000007;
typedef long long ll;
struct Mat {
    ll m[2][2];
} ans, base; //ans为答案矩阵， base为需要求次方的矩阵 
Mat Mul(Mat x, Mat y) { //返回矩阵x乘以矩阵y的矩阵 
    Mat c;
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            c.m[i][j] = 0;
            for (int k = 0; k < 2; k++) {
                c.m[i][j] += (x.m[i][k] % p * y.m[k][j] % p) % p;
            }
        }
    }
    return c;
}
void quick_pow(ll n) { //求base的n-1次方 
    while (n) { //同一般的快速幂 
        if (n & 1) {
            ans = Mul(ans, base);
        }
        base = Mul(base, base);
        n >>= 1;
    }
}
int main() {
    ll n;
    cin >> n;
    n %= 2000000016;
    ans.m[0][0] = 1, ans.m[0][1] = 0, ans.m[1][0] = 0, ans.m[1][1] = 1; //初始化ans为单位矩阵，
    base.m[0][0] = 1, base.m[0][1] = 1, base.m[1][0] = 1, base.m[1][1] = 0; //将base初始化为要求n次幂的矩阵
    quick_pow(n);
    cout << ans.m[0][1] % p << endl;
    return 0;
}