Problem of Precision

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 686    Accepted Submission(s): 386

Problem Description

 

 

Input

The first line of input gives the number of cases, T. T test cases follow, each on a separate line. Each test case contains one positive integer n. (1 <= n <= 10^9)

 

 

Output

For each input case, you should output the answer in one line.

 

 

Sample Input

3 1 2 5

 

 

Sample Output

9 97 841

 

 

Source

 

 

Recommend

lcy

 

 

 

 

 

 

#include
      
       #include
       
        #include
        
         using namespace std;const int mod=1024;struct Matrix{    int arr[2][2];};Matrix unit,init;Matrix Mul(Matrix a,Matrix b){    Matrix c;    for(int i=0;i<2;i++)        for(int j=0;j<2;j++){            c.arr[i][j]=0;            for(int k=0;k<2;k++)                c.arr[i][j]=(c.arr[i][j]+a.arr[i][k]*b.arr[k][j]%mod)%mod;            c.arr[i][j]%=mod;        }    return c;}Matrix Pow(Matrix a,Matrix b,int k){    while(k){        if(k&1){            b=Mul(b,a);        }        a=Mul(a,a);        k>>=1;    }    return b;}void Init(){    unit.arr[0][0]=5,   unit.arr[0][1]=2,   unit.arr[1][0]=unit.arr[1][1]=0;    init.arr[0][0]=init.arr[1][1]=5,    init.arr[0][1]=2,   init.arr[1][0]=12;}int main(){    //freopen("input.txt","r",stdin);    int t,n;    Init();    scanf("%d",&t);    while(t--){        scanf("%d",&n);        Matrix res=Pow(init,unit,n-1);        int ans=(2*res.arr[0][0]-1)%mod;    //注意这里，刚开始这里没有%mod，WA了好几次        printf("%d\n",ans);    }    return 0;}