题目链接:https://www.luogu.org/problemnew/show/P1939
时空限制 1000ms / 128MB

题目描述

a[1]=a[2]=a[3]=1;
a[x]=a[x-3]+a[x-1](x>3).
求a数列的第n项对1000000007（10^9+7）取余的值。

输入格式

第一行一个整数T，表示询问个数。
以下T行，每行一个正整数n。

输出格式

每行输出一个非负整数表示答案。

输入样例

3
6
8
10

输出样例

4
9
19

说明

对于30%的数据 n<=100;
对于60%的数据 n<=2*10^7;
对于100%的数据 T<=100，n<=2*10^9.

解题思路

矩阵快速幂的模板。这道题目的关键之处在于构造初始矩阵，题目都告诉我们了要用矩阵加速，所以矩阵快速幂是核心所在。
我们首先要确定目标矩阵。下面这个矩阵就是我想要的矩阵.[ A[i], A[i−1], A[i−2] ]​
那么这个矩阵要怎样算出来。显然可以由上一项求得:

A[i-1]      A[i]
A[i-2] ---> A[i-1]
A[i-3]      A[i-2]

根据题目给出的递推式可以得到下面三个式子:

A[i] = A[i-1]*1 + A[i-2]*0 + A[i-3]*1
A[i-1] = A[i-1]*1 + A[i-2]*0 + A[i-3]*0
A[i-2] = A[i-1]*0 + A[i-2]*1 + A[i-3]*0

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

1 1 0
0 0 1
1 0 0

然后我们就可以通过矩阵快速幂进行求解。
值得注意的是，应该从第4项开始计算，即这个矩阵的N次方算出来的第一个元素是A[N+3],这样的话我们可以直接算N-3次就行了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
struct Mat {
    ll m[5][5];
}ans, a;
Mat Mul(Mat a, Mat b, int n) {
    Mat c;
    memset(c.m, 0, sizeof(c.m));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= 3; j++)
            for (int k = 1; k <= 3; k++)
                c.m[i][j] = (c.m[i][j] + (a.m[i][k] * b.m[k][j]) % mod) % mod;
    return c;
}
int main() {
    int t, n;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        if (n <= 3) {
            printf("1\n");
            continue;
        }
        n -= 3;
        memset(ans.m, 0, sizeof(ans.m));
        memset(a.m, 0, sizeof(a.m));
        ans.m[1][1] = ans.m[1][2] = ans.m[1][3] = 1;
        a.m[1][1] = a.m[1][2] = a.m[2][3] = a.m[3][1] = 1;
        while (n) {
            if (n & 1)
                ans = Mul(ans, a, 1);
            a = Mul(a, a, 3);
            n >>= 1;
        }
        printf("%lld\n", ans.m[1][1]);
    }
    return 0;
}