Article From:https://www.cnblogs.com/lalalatianlalu/p/9733619.html

The title is to seek (sqrt (2) +sqrt (3)) ^ (2*n) to rend down and then to MOD1024.

Idea: It’s interesting, but I think it’s the only way I can do it, because the problem is so limited that we turn (sqrt (2) + sqrt (3)) into (5 + 2 * sqrt (6) ^ n

Let Sn = An + bn, An = (5 + 2 * sqrt (6) ^ n, Bn = (5-2 * sqrt (6) ^ n, we can find that Bn is less than 1, then our final answer is Sn-1 modelling

Then we construct Sn * ((5 + 2 * sqrt (6)) + (5-2 * sqrt (6))), and continue to simplify, we get Sn * 10 = Sn + 1-Sn-1, and then the matrix is exponentially fast.

Code:

```#include <cstdio>
using namespace std;
typedef long long LL;

const int MOD=1024;
///Assign values to R and C before use.
struct mat{
long long a[30][30];
int r,c;
mat operator *(const mat &b)const{
mat ret;
for (int i=0;i<r;i++){
for (int j=0;j<b.c;j++){
ret.a[i][j]=0;
for (int k=0;k<c;k++)
ret.a[i][j]+=a[i][k]*b.a[k][j],ret.a[i][j]%=MOD;
}
}
ret.r=r;
ret.c=b.c;
return ret;
}
void init_unit(int x)
{
r=c=x;
for(int i=0;i<r;i++){
for(int j=0;j<c;j++){
if(i==j)a[i][j]=1;
else a[i][j]=0;
}
}
}
}unit;
mat qmod(mat p,LL n){
unit.init_unit(p.c);
mat ans=unit;
while(n){
if(n&1)ans=p*ans;
p=p*p;
n>>=1;
}
return ans;
}

int main()
{
int T;
scanf("%d",&T);
while(T--){
int n;
scanf("%d",&n);
mat A;
A.r=2;A.c=2;
A.a[0][0]=10;A.a[0][1]=-1;
A.a[1][0]=1;A.a[1][1]=0;
mat B;
B.r=B.c=2;
B.a[0][0]=10;
B.a[1][0]=2;
mat ans;
ans.r=ans.c=2;
ans=qmod(A,n-1);
ans=ans*B;
printf("%lld\n",(ans.a[0][0]+MOD-1)%MOD);
}
return 0;
}```