1 // File Name: temp.cpp 2 // Author: darkdream 3 // Created Time: 2014年09月17日 星期三 11时35分45秒 4  5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque>10 #include<stack>11 #include<bitset>12 #include<algorithm>13 #include<functional>14 #include<numeric>15 #include<utility>16 #include<sstream>17 #include<iostream>18 #include<iomanip>19 #include<cstdio>20 #include<cmath>21 #include<cstdlib>22 #include<cstring>23 #include<ctime>24 #define LL long long25 #define m 100000000726 using namespace std;27 int n ; 28 struct Matrix29 {30    LL mat[20][20];31    void clear()32    {33       memset(mat,0,sizeof(mat));34    }35    void output()36    {37      for(int i =0  ;i < n ;i ++)38      {39        for(int j = 0 ;j < n ;j ++)40            printf("%I64d ",mat[i][j]);41      printf("\n");42      }43    }44    void init()45    {46        n = 2;47        clear();48        mat[0][0] = 3; 49        mat[0][1] = 1;50        mat[1][0] = 1;51        mat[1][1] = 3;52    }53    Matrix operator *(const Matrix &b) const54    {55        Matrix ret;56        ret.clear();57        for(int i = 0 ;i < n ;i ++)58            for(int j = 0;j < n;j ++)59            {60                for(int k = 0 ;k < n ;k ++)61                {62                  ret.mat[i][j] =(ret.mat[i][j] + mat[i][k] * b.mat[k][j]) % m ; // 第I 行  第J  列        63                }64            }65        return ret;66    }67 };68 Matrix Pow( Matrix a ,LL t )69 {70   Matrix ret;71   ret.clear();72   for(int i = 0 ;i < n ;i ++)73        ret.mat[i][i] = 1;74   Matrix tmp = a; 75   while(t)76   {77       if(t&1) ret = ret * tmp;78       tmp = tmp * tmp;79       t >>=1;80   }81   return ret;82 }83 int main(){84     LL l ; 85     while(scanf("%I64d",&l) != EOF)86     {87         if(l == 0)88         {89           printf("1\n");90           continue;91         }92         Matrix  a;93         a.init();94         a = Pow(a,l);95         printf("%I64d\n",a.mat[1][1]);96     }97     return 0;98 }