牛客编程巅峰赛S2赛季第3场第一题

这道题就是很明显的矩阵快速幂板子题了，根据 = = ,根据这个规律，可以把当做底数，相当于做矩阵快速幂，b数组也是一样的规律。

class Solution {

typedef long long ll;
public:
    /**
     * 返回c[n]%1000000007的值
     * @param n long长整型 即题目中的n
     * @return int整型
     */
    const int mod = 1e9+7;
    struct Matrix {
    ll a[2][2];
    int n, m; //矩阵行列
    friend Matrix operator * (Matrix a, Matrix b) {
        Matrix c; //临时矩阵
        const int mod = 1e9+7;
        memset(c.a, 0, sizeof(c.a));
        c.n = a.n, c.m = b.m; //俩矩阵相乘后的行和列
        for(int i = 0; i < a.n; i++)
            for(int j = 0; j < b.m; j++)
                for(int k = 0; k < a.m; k++)
                    c.a[i][j] = (c.a[i][j] + 1LL * a.a[i][k] * b.a[k][j]) % mod;
        return c;
    }
}A, f;
inline ll work1(ll n) { //f[i] = b*f[i-1] + c*f[i-2];
        f.n = 2, f.m = 1;  //原矩阵行列
        A.n = 2, A.m = 2;  //构造矩阵行列
        //原矩阵
        f.a[0][0] = 6;
        f.a[1][0] = 2;
        //for(int i = 0; i < n; i++) f.a[i][i] = 1;   //单位矩阵
        //构造的矩阵
        A.a[0][0] = 2;
        A.a[0][1] = 3;
        A.a[1][0] = 1;
        A.a[1][1] = 0;
        while(n) {
            if(n & 1) f = A * f;
            A = A * A, n >>= 1;
        }
        return f.a[0][0];
    }
    inline ll work2(ll n) { //f[i] = b*f[i-1] + c*f[i-2];
        f.n = 2, f.m = 1;  //原矩阵行列
        A.n = 2, A.m = 2;  //构造矩阵行列
        //原矩阵
        f.a[0][0] = 35;
        f.a[1][0] = 7;
        //for(int i = 0; i < n; i++) f.a[i][i] = 1;   //单位矩阵
        //构造的矩阵
        A.a[0][0] = 3;
        A.a[0][1] = 10;
        A.a[1][0] = 1;
        A.a[1][1] = 0;
        while(n) {
            if(n & 1) f = A * f;
            A = A * A, n >>= 1;
        }
        return f.a[0][0];
    }
    int Answerforcn(long long n) {
        // write code here
        if(n == 2) return 210;
        else if(n == 1) return 14;
        ll s = work1(n-2) * work2(n-2) % mod;
        return (int)s;
    }
};