GZOI2019 逼死强迫症

$$ \text{设}f\left( n \right) \text{表示}2\times n\text{的矩形的方案数。} \\ \text{设}g\left( n \right) \text{为}2\times n,\text{全部使用}1\times \text{2的砖块填充的方案数} \\ \text{转移则有}f\left( n \right) =f\left( n-1 \right) +f\left( n-2 \right) +2\sum_{1\le j\le n-2}{g\left( j-1 \right)}\left( \text{枚举在第}j\text{列放置第一个}1\times \text{1的块，第}n\text{列放置第二个} \right) \\ =f\left( n-1 \right) +f\left( n-2 \right) +\sum_{0\le j\le n-3}{g\left( j \right)} \\ \text{由}g\left( 0 \right) =g\left( 1 \right) =\text{1,}g\left( n \right) =g\left( n-1 \right) +g\left( n-2 \right) \text{知}\sum_{0\le j\le n-3}{g\left( j \right)}=g\left( n-1 \right) -1 \\ \text{故}f\left( n \right) =f\left( n-1 \right) +f\left( n-2 \right) +2g\left( n-1 \right) -2 \\ \,\,\text{构造矩阵} \\ M_1=\left[ \begin{matrix}{l} f\left( 1 \right)& f\left( 2 \right)& g\left( 1 \right)& g\left( 2 \right)& -2\\ \end{matrix} \right] \text{和转移矩阵}T=\left[ \begin{matrix}{l} 0& 1& 0& 0& 0\\ 1& 1& 0& 0& 0\\ 0& 0& 0& 1& 0\\ 0& 2& 1& 1& 0\\ 0& 1& 0& 0& 1\\ \end{matrix} \right] \\ \text{则}M_1T^{n-1}\text{即为结果矩阵。} \\ f\left( 1 \right) =f\left( 2 \right) =\text{0,}g\left( 1 \right) =\text{1,}g\left( 2 \right) =2 \\ $$

#include <cstring>
#include <iostream>
using int_t = long long int;
using std::cin;
using std::cout;
using std::endl;

const int_t mod = 1e9 + 7;

struct Matrix {
    int_t data[6][6];
    int_t n;
    Matrix(int_t n) : n(n) { memset(data, 0, sizeof(data)); }
    Matrix operator*(const Matrix& rhs) const {
        Matrix result(n);
        for (int_t i = 1; i <= n; i++) {
            for (int_t j = 1; j <= n; j++) {
                for (int_t k = 1; k <= n; k++) {
                    result.data[i][j] = (result.data[i][j] +
                                         data[i][k] * rhs.data[k][j] % mod) %
                                        mod;
                }
            }
        }
        return result;
    }
    Matrix pow(int_t index) {
        Matrix result(n), base = *this;
        for (int_t i = 1; i <= n; i++) result.data[i][i] = 1;
        while (index) {
            if (index & 1) result = result * base;
            base = base * base;
            index >>= 1;
        }
        return result;
    }
};

int main() {
    int_t T;
    cin >> T;
    Matrix trans(5);
    trans.data[1][2] = 1;
    trans.data[2][1] = 1;
    trans.data[2][2] = 1;
    trans.data[3][4] = 1;
    trans.data[4][2] = 2;
    trans.data[4][3] = 1;
    trans.data[4][4] = 1;
    trans.data[5][2] = 1;
    trans.data[5][5] = 1;
    Matrix M0(5);
    M0.data[1][3] = 1;
    M0.data[1][4] = 2;
    M0.data[1][5] = mod - 2;
    while (T--) {
        int_t n;
        cin >> n;
        if (n == 0)
            cout << 0 << endl;
        else {
            auto res = M0 * trans.pow(n - 1);
            cout << res.data[1][1] << endl;
        }
    }
    return 0;
}