矩阵快速幂 HDU5015

  1 #include <iostream>
  2 #include <cstring>
  3 
  4 using namespace std;
  5 
  6 long long tmp[11];
  7 
  8 //矩阵大小上限
  9 const int SIZ=100;
 10 int MOD=10000007;
 11 
 12 //矩阵大小为n*m，初始化全部为0
 13 struct mat
 14 {
 15     int n,m;
 16     long long ar[SIZ][SIZ];
 17     mat()
 18     {
 19         memset(ar,0,sizeof(ar));
 20         n=m=SIZ;
 21     };
 22 };
 23 
 24 //矩阵乘法
 25 mat operator *(mat a,mat b)
 26 {
 27     mat c;
 28     c=mat();
 29     c.n=a.n;
 30     c.m=b.m;
 31     for(int i=1;i<=a.n;i++)
 32         for(int j=1;j<=b.m;j++)
 33             for(int k=1;k<=a.m;k++)
 34             {
 35                 c.ar[i][j]+=(a.ar[i][k]*b.ar[k][j])%MOD;
 36                 c.ar[i][j]%=MOD;
 37             }
 38     return c;
 39 }
 40 
 41 //矩阵加法
 42 mat operator +(mat a,mat b)
 43 {
 44     mat c;
 45     c=mat();
 46     c.n=a.n;
 47     c.m=a.m;
 48     for(int i=1;i<=a.n;i++)
 49         for(int j=1;j<a.m;j++)
 50             c.ar[i][j]=a.ar[i][j]+b.ar[i][j];
 51     return c;
 52 }
 53 
 54 //矩阵快速幂
 55 mat operator ^(mat a,int k)
 56 {
 57     mat c;
 58     c=mat();
 59     c.n=a.n;
 60     c.m=a.m;
 61     for(int i=1;i<=a.n;i++)
 62         c.ar[i][i]=1;
 63     while(k)
 64     {
 65         if(k&1)
 66             c=c*a;
 67         a=a*a;
 68         k/=2;
 69     }
 70     return c;
 71 }
 72 
 73 int main()
 74 {
 75     int n,m;
 76     while(cin>>n>>m)
 77     {
 78         for(int i=1;i<=n;i++)
 79         {
 80             cin>>tmp[i];
 81         }
 82         mat mat1;
 83         mat1=mat();
 84         mat1.m=mat1.n=n+2;
 85         for(int i=1;i<mat1.m;i++)
 86         {
 87             for(int t=2;t<=i;t++)
 88             {
 89                 mat1.ar[i][t]=1;
 90             }
 91             mat1.ar[i][1]=10;
 92             mat1.ar[i][mat1.m]=1;
 93         }
 94         mat1.ar[mat1.m][mat1.m]=1;
 95         mat mat2 ;
 96         mat2 =mat();
 97         mat2.n=n+2;
 98         mat2.m=1;
 99         for(int i=2;i<mat2.n;i++)
100         {
101             mat2.ar[i][1]=tmp[i-1];
102         }
103         mat2.ar[1][1]=23;
104         mat2.ar[mat2.n][1]=3;
105         mat mat3;
106         mat3=(mat1^(m))*mat2;
107         cout<<mat3.ar[n+1][1]<<endl;
108     }
109     return 0;
110 }
View Code