1 //Accepted    220 KB    359 ms  2 #include <cstdio>  3 #include <cstring>  4 const int maxn=5;  5 int pp;  6 struct matrix  7 {  8     //矩阵m*n  9     //(0,0)..(m-1,n-1) 10     int a[maxn][maxn]; 11     int m,n; 12     matrix() 13     { 14         memset(a,0,sizeof(a)); 15         m=n=0; 16     } 17     matrix operator+(matrix mymatrix) 18     { 19         matrix m_matrix; 20         int i,j; 21         for (i=0;i<m;i++) 22         for (j=0;j<n;j++) 23         m_matrix.a[i][j]=(a[i][j]+mymatrix.a[i][j])%pp; 24         m_matrix.m=m; 25         m_matrix.n=n; 26         return m_matrix; 27     } 28     matrix operator*(matrix mymatrix) 29     { 30         matrix m_matrix; 31         int i,j,k; 32         for (i=0;i<m;i++) 33         { 34             for (j=0;j<n;j++) 35             { 36                 if (a[i][j]) 37                 for (k=0;k<mymatrix.n;k++) 38                 m_matrix.a[i][k]=(m_matrix.a[i][k]+a[i][j]*mymatrix.a[j][k])%pp; 39             } 40         } 41         m_matrix.m=m; 42         m_matrix.n=mymatrix.n; 43         return m_matrix; 44     } 45     //A^k 46     matrix getp(int k) 47     { 48         matrix d,c; 49         if (k==1) return *this; 50         if (k==2) return (*this)*(*this); 51         d=getp(k/2); 52         if (k%2==0) return d*d; 53         else 54         return d*d*(*this); 55     } 56     //A+A^2+A^3+..+A^k 57     matrix sump(int k) 58     { 59         matrix d,c; 60         if (k==1) return *this; 61         if (k==2) return (*this)+(*this)*(*this); 62         d=sump(k/2); 63         if (k%2==0) 64         { 65             return d+d*getp(k/2); 66         } 67         else 68         return d+d*getp(k/2)+getp(k); 69     } 70     void output() 71     { 72         int i,j; 73         for (i=0;i<m;i++) 74         { 75             for (j=0;j<n;j++) 76             printf("%d ",a[i][j]%pp); 77             printf("\n"); 78         } 79     } 80     void input() 81     { 82         for (int i=0;i<m;i++) 83         { 84             for (int j=0;j<n;j++) 85             { 86                 scanf("%d",&a[i][j]); 87             } 88         } 89     } 90 }; 91 int n; 92 int k; 93 matrix tr,mtr; 94 int main() 95 { 96     pp=2009; 97     int T; 98     scanf("%d",&T); 99     for (int t=1;t<=T;t++)100     {101         scanf("%d",&n);102         printf("Case %d: ",t);103         if (n<3)104         {105             if (n==0) printf("1\n");106             if (n==1) printf("4\n");107             if (n==2) printf("9\n");108             continue ;109         }110         tr.m=tr.n=4;111         tr.a[0][0]=1;112         tr.a[0][1]=tr.a[0][2]=tr.a[0][3]=0;113         tr.a[1][0]=1;114         tr.a[1][1]=3;115         tr.a[1][2]=1;116         tr.a[1][3]=0;117         tr.a[2][0]=0;118         tr.a[2][1]=2;119         tr.a[2][2]=0;120         tr.a[2][3]=1;121         tr.a[3][0]=0;122         tr.a[3][1]=7;123         tr.a[3][2]=0;124         tr.a[3][3]=0;125         tr=tr.getp(n-1);126         mtr.m=1;127         mtr.n=4;128         mtr.a[0][0]=4;129         mtr.a[0][1]=5;130         mtr.a[0][2]=3;131         mtr.a[0][3]=1;132         tr=mtr*tr;133         printf("%d\n",tr.a[0][0]);134     }135     return 0;136 }