题意:求[(2+3)2n]mod1024[(\sqrt{2}+\sqrt{3})^{2n}] mod 1024

分析: 把指数的2带入 原式等于 [(5+26)n][(5+2\sqrt{6})^n]

有一个重要的结论是n次运算后其结果最终形式也是an+bn6a_n+b_n\sqrt{6} 的形式

记最终的解

F(n)=an+bn6F(n) = a_n+b_n\sqrt{6} F(n1)=an1+bn16F(n-1) = a_{n-1}+b_{n-1}\sqrt{6} F(n)F(n1)=5+26\frac{F(n)}{F(n-1)} = 5+2\sqrt{6} F(n)=(5+26)F(n1)F(n) = (5+2\sqrt{6})F(n-1) F(n)=(5+26)an1+(56+12)bn1F(n) = (5+2\sqrt{6})a_{n-1}+(5\sqrt{6}+12)b_{n-1} F(n)=an+bn6F(n) = a_n+b_n\sqrt{6} an=(5+26)an1a_n = (5+2\sqrt{6})a_{n-1} bn6=(56+12)bn1b_n\sqrt{6} = (5\sqrt{6}+12)b_{n-1} an+bn6=(5an1+12bn1)+(2an1+5bn1)6a_n+b_n\sqrt{6} = (5a_{n-1}+12b_{n-1})+(2a_{n-1}+5b_{n-1})\sqrt{6}

这就是实部和虚部的递推式

(5+26)n+(526)n=2an(5+2\sqrt{6})^n+(5-2\sqrt{6})^n = 2a_n (526)n0(5-2\sqrt{6})^n≈0

所以原式向下取整就是[(2+3)2n]=2an1[(\sqrt{2}+\sqrt{3})^{2n}] = 2a_n-1

inline ll mod(ll a){return a%MOD;}
struct Matrix{
	ll mt[22][22],r,c;
	void init(int rr,int cc,bool flag=0){
		r=rr;c=cc;
		memset(mt,0,sizeof mt);
		if(flag) rep(i,1,r) mt[i][i]=1;
	}
	Matrix operator * (const Matrix &rhs)const{
		Matrix ans; ans.init(r,rhs.c);
		rep(i,1,r){
			rep(j,1,rhs.c){
				int t=max(r,rhs.c);
				rep(k,1,t){
					ans.mt[i][j]+=mod(mt[i][k]*rhs.mt[k][j]);
					ans.mt[i][j]=mod(ans.mt[i][j]);
				}
			}
		}
		return ans;
	}
};
Matrix fpw(Matrix A,int n){
	Matrix ans;ans.init(A.r,A.c,1);
	while(n){
		if(n&1) ans=ans*A;
		n>>=1;
		A=A*A;
	}
	return ans;
}

int bas[3][3]={
	{0,0,0},
	{0,5,12},
	{0,2,5},
};
int bas2[]={0,5,2}; 
int main(){
	Matrix A;A.init(2,2);
	rep(i,1,2) rep(j,1,2) A.mt[i][j]=bas[i][j];
	Matrix b; b.init(2,1);
	rep(i,1,2) b.mt[i][1]=bas2[i];
	int T=read();
	while(T--){
		int n=read();
		Matrix res=fpw(A,n-1); res=res*b;
		ll ans=mod(2*res.mt[1][1]-1+MOD);
		println(ans);
	}
	return 0;
}