题解 | #斐波那契数列问题的递归和动态规划3#

• 递推式f[n] = f[n - 1] + f[n -3]，即第n年的牛个数等于上一年的牛个数+三年前的牛个数（三年前的牛到今年每个都会生一个仔）
• 一切线性递推式都可以表示为Y=AX的形式，然后就可以使用矩阵快速幂求解

#include <iostream>
#include <vector>
using namespace std;
const int MOD = 1e9 + 7;
// f[n] = f[n - 1] + f[n - 3]
/*
f[n]     1 0 1     f[n - 1]
f[n - 1] 1 0 0     f[n - 2]
f[n - 2] 0 1 0     f[n - 3]
*/
// f[0] = 1, f[1] = 1, f[2] = 1, f[3] = 2, 
// f[4] = 3, f[5] = 4, f[6] = 6, f[7] = 9
typedef vector<long long> vll;
vector<vll> f = {{1, 0, 1}, {1, 0, 0}, {0, 1, 0}};
vector<vll> mul(vector<vll> &a, vector<vll> &b){
    vector<vll> c = {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}};
    for(int i = 0; i < 3; i ++ )
        for(int j = 0; j < 3; j ++ )
            for(int k = 0; k < 3; k ++ )
                c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % MOD;
    return c;
}
int main()
{
    long long n; cin >> n;
    n ++ ;
    vector<vll> c = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}};
    while(n > 0){
        if(n & 1) c = mul(c, f);
        f = mul(f, f);
        n = n >> 1;
    }
    cout << c[0][0] << endl;
    return 0;
}