hdu 2256 Problem of Precision

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #define mod 1024
 6 #define ll long long
 7 #define nn 2
 8 using namespace std;
 9 struct rec{
10     ll v[nn][nn];
11     rec(){memset(v,0,sizeof v);}
12 };
13 rec mul(rec a,rec b){
14     rec ans;
15     ll sum;
16     for(int k=0;k<nn;k++){
17        for(int i=0;i<nn;i++){
18           for(int j=0;j<nn;j++){
19               sum=a.v[i][k]*b.v[k][j]%mod;
20               ans.v[i][j]=(ans.v[i][j]+sum)%mod;
21           }
22        }
23     }
24     return ans;
25 }
26 rec pow(rec a,int n){
27     if(n==1) return a;
28     rec ans=pow(a,n/2);
29     ans=mul(ans,ans);
30     if(n&1) return mul(ans,a);
31     else return ans;
32 }
33 int t,n;
34 int gao(rec a){
35     return (((a.v[0][0]*5%mod+a.v[0][1]*2%mod)*2-1)%mod+mod)%mod;
36 }
37 int main(){
38     scanf("%d",&t);
39     while(t--){
40         scanf("%d",&n);
41         rec a;
42         if(n==1) {cout<<9<<endl;continue;}
43         a.v[0][0]=5,a.v[0][1]=12;
44         a.v[1][0]=2,a.v[1][1]=5;
45         a=pow(a,n-1);
46         printf("%d
",gao(a));
47     }
48     return 0;
49 }
hdu2256