洛谷 [P1939] 矩阵加速数列

矩阵快速幂模版

#include <iostream>

#include <cstring>

#include <cstdlib>

#include <algorithm>

#include <cstdio>

#include <cmath>

#define ll long long

using namespace std;

const int MOD = (int) 1e9+7;

struct Matrix {

	static const int MAXN = 3;

	ll num[MAXN][MAXN], col, row;

	void clear() {

		memset(num, 0, sizeof(num));

		col = row = 0;

	}

	void unit() {

		col = row = 3;

		for(int i = 0; i < MAXN; i++) num[i][i] = 1;

	}

	void build(){

		col = row = 3;

		num[1][0] = num[2][1] = num[0][2] = num[2][2] = 1;

	}

};

Matrix operator * (const Matrix & a, const Matrix & b){

	Matrix res;

	res.clear();

	for(int i = 0; i < 3; i++) {

		for(int j = 0; j < 3; j++) {

			for(int k = 0; k < 3; k++) {

				(res.num[i][j] += a.num[i][k] * b.num[k][j]) %= MOD;

			}

		}

	}

	return res;

}

Matrix operator ^ (Matrix a, ll k) {

	Matrix res;

	res.clear(); res.unit();

	while(k) {

		if(k & 1ll) res = res * a;

		a = a * a;

		k >>= 1;

	}

	return res;

}

ll T, n;

int main() {

	cin>>T;

	while(T--) {

		cin>>n;

		if(n <= 3) {cout<<1<<endl;continue;}

		n -= 3;

		Matrix a;

		a.clear(); a.build();

		a = a ^ n;

		ll ans = 0;

		for(int i = 0; i < 3; i++)  ans += a.num[i][2];

		ans %= MOD;

		cout<<ans<<endl;

	}

	return 0;

}

巴特西

洛谷 [P1939] 矩阵加速数列

矩阵快速幂模版

最新文章

热门文章