如代码所示，时间复杂度logn

#include <iostream>
#include <vector>
using namespace std;

typedef long long ll;
typedef vector<vector<ll>> mat;

mat mul(mat a, mat b) {
	mat res(a.size(), vector<ll>(b[0].size(), 0));
	for (int i = 0; i < a.size(); i++)
		for (int k = 0; k < b.size(); k++)
			if (a[i][k])
				for (int j = 0; j < b[0].size(); j++)
					res[i][j] += a[i][k] * b[k][j];
	return res;
}

mat pow(mat a, ll p) {
	mat res(a.size(), vector<ll>(a.size(), 0));
	for (int i = 0; i < a.size(); i++) res[i][i] = 1;
	while (p) {
		if (p & 1) res = mul(res, a);
		a = mul(a, a);
		p >>= 1;
	}
	return res;
}

ll solve(ll n) {
	if (n == 1) return 1;
	mat M = {{1,4,0}, {0,1,1}, {0,0,1}};
	mat V = {{1}, {1}, {1}};
	mat Mpow = pow(M, n-1);
	mat res = mul(Mpow, V);
	return res[0][0];
}

int main() {
	ios::sync_with_stdio(false),cin.tie(0);ll n;
	cin >> n;
	while( n--){
		int x;
		cin >> x;
...