数列 (seq. cpp/c/pas)

题目描述

a [1]=a [2]=a [3]=1

a [x]=a [x-3]+a [x-1] (\(x \gt 3\))

求 a 数列的第 n 项对 1000000007 (\(10^9 + 7\)) 取余的值.

输入格式

第一行一个整数 T, 表示询问个数.

以下 T 行, 每行一个正整数 n.

输出格式

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

样例输入

3
6
8
10

样例输出

4
9
19

数据范围

对于 30% 的数据 \(n \leq 100\);

对于 60% 的数据 \(n \leq 2 \times 10^7\);

对于 100% 的数据 \(T \leq 100, n \leq 2 \times 10^9\);

Explanation

矩阵快速幂应该还是可以水一发的~

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
typedef long long lli;
const lli modr = 1000000007ll;

class Matrix {
public:
    lli dat[4][4];
    Matrix(void) {
        for (int i = 1; i <= 3; i++)
            for (int j = 1; j <= 3; j++)
                this->dat[i][j] = 0;
        return ;
    }
    Matrix(lli a, lli b, lli c) : Matrix() {
        this->dat[1][1] = a;
        this->dat[2][2] = b;
        this->dat[3][3] = c;
        return ;
    }
    Matrix(lli a) : Matrix(a, a, a) { return ; }
    Matrix(lli a[][4]) : Matrix() {
        for (int i = 1; i <= 3; i++)
            for (int j = 1; j <= 3; j++)
                this->dat[i][j] = a[i][j];
        return ;
    }
};

Matrix operator + (Matrix a, Matrix b) {
    Matrix c;
    for (int i = 1; i <= 3; i++)
        for (int j = 1; j <= 3; j++)
            c.dat[i][j] = a.dat[i][j] + b.dat[i][j];
    return c;
}

Matrix operator * (Matrix a, Matrix b) {
    Matrix c;
    for (int i = 1; i <= 3; i++)
        for (int j = 1; j <= 3; j++) {
            c.dat[i][j] = 0;
            for (int k = 1; k <= 3; k++)
                c.dat[i][j] += a.dat[i][k] * b.dat[k][j];
            c.dat[i][j] %= modr;
        }
    return c;
}

Matrix operator ^ (Matrix a, lli b) {
    Matrix c(1);
    for (lli d = 1; d <= b; d <<= 1) {
        if ((b & d) > 0)
            c = c * a;
        a = a * a;
    }
    return c;
}

ostream& operator << (ostream& out, Matrix a) {
    for (int i = 1; i <= 3; i++) {
        for (int j = 1; j <= 3; j++)
            out << a.dat[i][j] << ' ';
        out << std::endl;
    } return out;
}
int T;
lli n;

int main(int argc, char** argv)
{
    scanf("%d", &T);
    for (int idx = 1; idx <= T; idx++) {
        scanf("%lld", &n);
        n -= 3;
        lli def_matr[4][4] = {
            {0, 0, 0, 0},
            {0, 1, 1, 1},
            {0, 1, 1, 1},
            {0, 1, 1, 1}
        }; Matrix a(def_matr);
        lli init_matr[4][4] = {
            {0, 0, 0, 0},
            {0, 0, 0, 1},
            {0, 1, 0, 0},
            {0, 0, 1, 1}
        }; Matrix b(init_matr);
        Matrix c = a * (b ^ n);
        printf("%lld\n", c.dat[3][3]);
    }
    return 0;
}