Luogu 矩阵加速（数列）

题解

---

题面

$a[1]=a[2]=a[3]=1$
$a[x]=a[x-3]+a[x-1] (x>3)$
求 $a$ 数列的第 $n$ 项对 $10^9$ 取余的值。
$n <= 20^9$

解

由于数据非常大，所以 $O(n)$ 的递推显然不能满足要求
矩阵加速模板题

$$矩阵 A = \left( \begin{matrix} a_1 & a_2 & a3 \end{matrix} \right)$$
$$矩阵 B = \left( \begin{matrix} a_2 & a_3 & a_4 \end{matrix} \right)$$
解出一个矩阵 $T$ 使得 $A * T = B$
显然
$$T = \left( \begin{matrix} 0 & 0 & 1\\ 1 & 0 & 0\\ 0 & 1 & 1\\ \end{matrix} \right)$$
考虑得到这样一个矩阵 $Ans$
$$Ans = A * T ^ {Pow - 3}$$
显然 $Ans_{1,3}$ 就是数列的第 $n$ 项
由于矩阵乘法满足结合律，所以快速幂计算 $T^{Pow - 3}$ 即可优化递推的时间复杂度
每次时间复杂度为 $O(log Pow)$

---

Code

#include <iostream>
#include <cstdio>
#include <cstring>
const int N = 10;
const int Mod = 1e9 + 7;
int n;
struct Node{
    long long m[N][N];
    Node() {memset(m,0,sizeof m);}
    void Clear() {for(int i = 1; i <= 3; i ++) m[i][i] = 1;}
};
Node operator * (const Node & a, const Node & b) {
    Node ret;
    for(int i = 1; i <= 3; i ++)
        for(int j = 1; j <= 3; j ++)
            for(int k = 1; k <= 3; k ++)
                ret.m[i][j] = (ret.m[i][j] + a.m[i][k] * b.m[k][j] % Mod) % Mod;
    return ret;
}
Node Ksm(Node a, int Pow) {
    Node ret; ret.Clear();
    while(Pow) {
        if(Pow & 1) ret = ret * a;
        a = a * a;
        Pow >>= 1;
    }
    return ret;
}
int main() {
    std:: cin >> n;
    for(int i = 1; i <= n; i ++) {
        int Pow; std:: cin >> Pow; Pow -= 3;
        if(Pow < 1) {std:: cout << 1 <<"\n"; continue ;}
        Node A;
        A.m[1][1] = 0, A.m[1][2] = 0, A.m[1][3] = 1;
        A.m[2][1] = 1, A.m[2][2] = 0, A.m[2][3] = 0;
        A.m[3][1] = 0, A.m[3][2] = 1, A.m[3][3] = 1;
        Node B = Ksm(A, Pow);
        Node Ans;
        Ans.m[1][1] = Ans.m[1][2] = Ans.m[1][3] = 1;
        Ans = Ans * B;
        std:: cout << Ans.m[1][3] << "\n";
    }
    return 0;
}