RT，P1939，80分

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int m=1000000007;
class Matrix {
	public:
		int x[30][30];
		int width,height;
		Matrix(int x,int y):width(x),height(y){};
		Matrix operator *(Matrix a) {
			Matrix b(a.width,height);
			for(int i=0;i<a.width;i++){
				for(int j=0;j<height;j++){
					b.x[i][j]=0;
					for(int k=0;k<3;k++){
						b.x[i][j]+=x[i][k]*a.x[k][j];
						b.x[i][j]%=m;
					}
				}
			}
			return b;
		}
};
int pow(int n) {
	Matrix p(3,3),ans(1,3);
	p.x[0][0]=p.x[2][0]=p.x[0][1]=p.x[1][2]=1;
	p.x[1][0]=p.x[1][1]=p.x[2][1]=p.x[0][2]=p.x[2][2]=0;
	ans.x[0][0]=ans.x[0][1]=ans.x[0][2]=1;
	n--;
	for(int i=1;i<n;i*=2){
		if(n&i){
			ans=ans*p;
		}
		p=p*p;
	}
	return ans.x[0][2];
}
signed main() {
	int t;
	cin>>t;
	while(t--){
		int n;
		cin>>n;
		cout<<pow(n)<<'\n';
	}
	return 0;
}

Hack数据:

1
9