hdu 1588【Gauss Fibonacci】

表示这一题可以直接用4*4矩阵做，前提是看了解题报告来着。。。http://blog.csdn.net/lansetiankong_yiyi/article/details/5828239这个解题报告的第二种方法令我佩服，灵活应用了矩阵，关键是构造矩阵这一块我不太会

我们来设置这样一个矩阵

B I

O I

其中O是零矩阵，I是单位矩阵

将它乘方，得到

B^2 I+B

O I

乘三方，得到

B^3 I+B+B^2

O I

乘四方，得到

B^4 I+B+B^2+B^3

O I

这个矩阵构造的令我佩服，记住了。。。

然后这个矩阵的实现可以直接用4*4矩阵。。。

然后呢，就是代码。。。

代码如下：

  1 #include <cstdio>
  2 #include <cstring>
  3 
  4 typedef __int64 ll;
  5 const int size = 4;
  6 
  7 struct matrix
  8 {
  9     ll a[size][size];
 10 };
 11 
 12 ll K,b,n,mod;
 13 
 14 void zero_matrix(matrix &x)
 15 {
 16     memset(x.a,0,sizeof(x.a));
 17 }
 18 
 19 void one_matrix(matrix &x)
 20 {
 21     zero_matrix(x);
 22     for(int i = 0;i < size;i ++)
 23     {
 24         x.a[i][i] = 1;
 25     }
 26 }
 27 
 28 matrix mul_matrix(matrix &x,matrix &y)
 29 {
 30     matrix ans;
 31 
 32     for(int i = 0;i < size;i ++)
 33     {
 34         for(int j = 0;j < size;j ++)
 35         {
 36             ans.a[i][j] = 0;
 37             for(int k = 0;k < size;k ++)
 38             {
 39                 ans.a[i][j] += x.a[i][k] * y.a[k][j] % mod;
 40             }
 41             ans.a[i][j] %= mod;
 42         }
 43 
 44     }
 45 
 46     return ans;
 47 }
 48 
 49 matrix pow_matrix(matrix x,ll pow)
 50 {
 51     matrix ans;
 52 
 53     one_matrix(ans);
 54 
 55     for(;pow;pow >>= 1)
 56     {
 57         if(pow & 1)
 58         {
 59             ans = mul_matrix(ans,x);
 60         }
 61 
 62         x = mul_matrix(x,x);
 63     }
 64 
 65     return ans;
 66 }
 67 
 68 int main()
 69 {
 70     while(scanf("%I64d%I64d%I64d%I64d",&K,&b,&n,&mod) == 4)
 71     {
 72         matrix fib;
 73         zero_matrix(fib);
 74         fib.a[0][0] = 0;
 75         fib.a[0][1] = fib.a[1][1] = fib.a[1][0] = 1;
 76         matrix ans1 = pow_matrix(fib,b);
 77         matrix base = pow_matrix(fib,K);
 78 
 79         for(int i = 0;i < 4;i ++)
 80         {
 81             for(int j = 2;j < 4;j ++)
 82             {
 83                 base.a[i][j] = (i == j);
 84             }
 85         }
 86         base.a[0][2] = base.a[1][3] = 1;
 87         for(int i = 2;i < 4;i ++)
 88         {
 89             for(int j = 0;j < 2;j ++)
 90             {
 91                 base.a[i][j] = 0;
 92             }
 93         }
 94 
 95         matrix tmp = pow_matrix(base,n);
 96         matrix temp;
 97         zero_matrix(temp);
 98         for(int i = 0;i < 2;i ++)
 99         {
100             for(int j = 0;j < 2;j ++)
101             {
102                 temp.a[i][j] = tmp.a[i][j+2];
103             }
104         }
105         matrix ans = mul_matrix(ans1,temp);
106         printf("%I64d\n",ans.a[1][0]);
107     }
108 
109     return 0;
110 }