P1939 【模板】矩阵加速（数列）

题目传送门

解题思路
这道题目的关键之处在于构造初始矩阵，题目都告诉我们了要用矩阵加速。所以矩阵快速幂是核心所在。

如何构造
我们首先要确定目标矩阵。下面这个矩阵就是我想要的矩阵.

\[\begin{bmatrix} F[i] \\ F[i-1] \\ F[i-2] \end{bmatrix} \]

那么这个矩阵要怎样算出来。根据题目给出的递推式可以得到下面三个式子
\(f[i] = f[i-1] \times 1 + f[i-2] \times 0 + f[i-3] \times 1\)

\(f[i-1] = f[i-1] \times 1 + f[i-2] \times 0 + f[i-3] \times 0\)

\(f[i-2] = f[i-1] \times 0 + f[i-2] \times 1 + f[i-3] \times 0\)

通过每一项的系数可以得出初始矩阵为

\[\begin{bmatrix} 1 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix} \]

然后我们就可以通过矩阵快速幂进行求解。

二、实现方法I

#include 
using namespace std;
typedef long long LL;
const int MOD = 1e9 + 7;
const int N = 10;
int n;
LL res[N][N], base[N][N];

inline void init() {
    //结果矩阵清零
    memset(res, 0, sizeof(res));
    //只记录f(i),f(i-1),f(i-2)共3个,所以初始化一个3*3矩阵即可
    for (int i = 1; i <= 3; i++) res[i][i] = 1;
    // base数组，原理见题解
    memset(base, 0, sizeof(base));
    base[1][1] = base[1][3] = base[2][1] = base[3][2] = 1;
}
//矩阵乘法
inline void mul(LL C[][N], LL A[][N], LL B[][N]) {
    static LL tmp[N][N];
    memset(tmp, 0, sizeof(tmp));
    for (int i = 1; i <= 3; i++)
        for (int j = 1; j <= 3; j++)
            for (int k = 1; k <= 3; k++) {
                tmp[i][j] += (A[i][k] % MOD) * (B[k][j] % MOD);
                tmp[i][j] %= MOD;
            }
    memcpy(C, tmp, sizeof tmp);
}
//快速幂
inline void qmi(int k) {
    while (k) {
        if (k & 1) mul(res, res, base);
        mul(base, base, base);
        k >>= 1;
    }
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        cin >> n;
        if (n <= 3) {
            printf("1\n");
            continue;
        }
        init();
        qmi(n - 1);
        printf("%lld\n", res[1][1]);
    }
}

三、实现方法II

#include 
using namespace std;
// https://www.luogu.com.cn/blog/wlz123/solution-p1939
typedef long long LL;
const int MOD = 1e9 + 7;
const int N = 10;
int n;

//矩阵声明
struct JZ {
    LL m[N][N];
} res, base;

inline void init() {
    //结果矩阵清零
    memset(res.m, 0, sizeof(res.m));
    //只记录f(i),f(i-1),f(i-2)共3个,所以初始化一个3*3矩阵即可
    for (int i = 1; i <= 3; i++) res.m[i][i] = 1;
    // base数组，原理见题解
    memset(base.m, 0, sizeof(base.m));
    base.m[1][1] = base.m[1][3] = base.m[2][1] = base.m[3][2] = 1;
}
//矩阵乘法
inline JZ mul(JZ A, JZ B) {
    JZ C;
    memset(C.m, 0, sizeof(C.m));
    for (int i = 1; i <= 3; i++)
        for (int j = 1; j <= 3; j++)
            for (int k = 1; k <= 3; k++) {
                C.m[i][j] += (A.m[i][k] % MOD) * (B.m[k][j] % MOD);
                C.m[i][j] %= MOD;
            }
    return C;
}
//快速幂
inline void qmi(int k) {
    while (k) {
        if (k & 1) res = mul(res, base);
        base = mul(base, base);
        k >>= 1;
    }
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        cin >> n;
        if (n <= 3) {
            printf("1\n");
            continue;
        }
        init();
        qmi(n - 1);
        printf("%lld\n", res.m[1][1]);
    }
}