R??G??B??

题目描述

msy 的“显示器”终于完工啦！但是由于设计出了问题，这个“显示器”存在一个严重的 bug，就是每个像素同时只能显示红色、绿色、蓝色其中的一种颜色。msy 感觉一个学期白忙活了，但是又不能浪费材料，于是他觉得把这个有问题的“显示器”作为装饰。msy 喜欢蓝色和绿色，同时也喜欢偶数，因此他希望“显示器”的每一帧都同时包含偶数个蓝色像素和偶数个绿色像素。此时 msy 想知道，他可以看到多少不同的帧？
由于答案可能很大，你只需输出答案对 $998244353$ 取模的结果即可。

输入格式

第一行一个数 $T(1\le T\le 100)$，表示数据组数。
接下来 $T$ 行，每行一个整数 $n(1\le n\le 10^9)$，表示“显示器”上的像素个数。

输出格式

输出 $T$ 行，表示每组数据的答案。

测试用例

输入

6
1
2 
3
4
5
1000000000

输出

1
3
7
21
61
224965630

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MAXN 1000005

//矩阵快速幂
const ll N = 3;   //方阵的大小
ll mod = 998244353;  //模
struct Matrix {
    ll x[N][N];
    Matrix() {
        memset(x, 0, sizeof(x));
    }
    Matrix(const Matrix &b) {
        memcpy(x, b.x, sizeof(x));
    }
    Matrix operator*(const Matrix &b) const {
        Matrix c;
        for (ll i = 0; i < N; i++)
            for (ll j = 0; j < N; j++) {
                c.x[i][j] = 0;
                for (ll k = 0; k < N; k++) {
                    c.x[i][j] += x[i][k] * b.x[k][j] % mod;
                    c.x[i][j] %= mod;
                }
            }
        return c;
    }
};

Matrix fastpow(Matrix a, ll n) {
    Matrix res;
    for (ll i = 0; i < N; i++)
        res.x[i][i] = 1;
    while (n) {
        if (n & 1) res = res * a;
        a = a * a;
        n >>= 1;
    }
    return res;
}

int main() {
    ll t, n;
    cin >> t;
    Matrix a, b;
    a.x[0][0] = 1;
    a.x[0][2] = 1;
    a.x[1][1] = 1;
    a.x[1][2] = 1;
    a.x[2][0] = 2;
    a.x[2][1] = 2;
    a.x[2][2] = 1;
    for (ll i = 1; i <= t; ++i) {
        cin >> n;
        b=fastpow(a, n-1);
        cout<<(b.x[0][0]%mod+((b.x[0][2]%mod)*2)%mod)%mod<<"\n";
    }

    return 0;
}