矩阵乘法快速幂 cojs 1717. 数学序列

矩阵乘法模板：

 #define N 801

 #include<iostream>

 using namespace std;

 #include<cstdio>

 int a[N][N],b[N][N],c[N][N];

 int n,m,p;

 int read()

 {

     int ans=,ff=;char s;

     s=getchar();

     while(s<''||s>'')

     {

         if(s=='-') ff=-;

         s=getchar();

     }

     while(s>=''&&s<='')

     {

         ans=ans*+s-'';

         s=getchar();

     }

     return ans*ff;

 }

 int main()

 {

     n=read();

     p=read();

     m=read();

     for(int i=;i<=n;++i)

       for(int j=;j<=p;++j)

       a[i][j]=read();

     for(int i=;i<=p;++i)

       for(int j=;j<=m;++j)

       b[i][j]=read();

      for(int i=;i<=n;++i)

       {

            for(int j=;j<=m;++j)

        {

            c[i][j]=;

            for(int k=;k<=p;++k)

            c[i][j]+=a[i][k]*b[k][j];

            printf("%d ",c[i][j]);

        }

        printf("\n");

       }

     return ;

  } 

cojs 1717. 数学序列

★   输入文件：number1.in   输出文件：number1.out   简单对比
时间限制：1 s   内存限制：128 MB

【题目描述】

已知一个函数f :

f (1) =1

f (2) =1

f (n) = (a × f (n −1) +b × f (n − 2))mod 7

现给出a,b,n ,要你求出 f (n) .

【输入格式】

每一行输入一组数据分别为A,B,N(1<=A,B<=1000,1<=N<=200000000)

【输出格式】

每一行输出结果 f (n) .

【样例输入】

1 1 3

1 2 10

【样例输出】

2

5

 #include<iostream>

 using namespace std;

 #include<cstdio>

 #include<cstring>

 #define N 5

 #define mod 7

 struct Jz{

     int line,cal;

     int jz[N][N];

 }a,ans;

 int A,B;

 void pre_chuli()

 {

     a.cal=;a.line=;

     a.jz[][]=;a.jz[][]=;

     a.jz[][]=B;a.jz[][]=A;

     ans.cal=;ans.line=;

     ans.jz[][]=;

     ans.jz[][]=;

 }

 Jz matrax(Jz x,Jz y)

 {

     Jz sum;

     sum.line=x.line;sum.cal=y.cal;

     memset(sum.jz,,sizeof(sum.jz));

     /* for(int i=1;i<=sum.line;++i)

     {

      for(int j=1;j<=sum.cal;++j)

          printf("%d ",sum.jz[i][j]);

       printf("\n");

     }*/

     for(int i=;i<=sum.line;++i)

       for(int j=;j<=sum.cal;++j)

       {

           for(int k=;k<=x.cal;++k)

           {

               sum.jz[i][j]=(sum.jz[i][j]+x.jz[i][k]*y.jz[k][j])%mod;

           }

       }

     return sum;

 }

 int Fast_matrax(int n)

 {

     if(n==) return ans.jz[][];

     n-=;/*真正的乘法次数是n-2*/

     while(n)

     {

         if(n&)

         {

             ans=matrax(a,ans);

         }

         n>>=;

         a=matrax(a,a);

     }

     return ans.jz[][]%mod;

 }

 int main()

 {

     freopen("number1.in","r",stdin);

     freopen("number1.out","w",stdout);

     int n;

     while(scanf("%d%d%d",&A,&B,&n)==)

     {

         memset(a.jz,,sizeof(a.jz));

         a.cal=a.line=;

         memset(ans.jz,,sizeof(ans.jz));

         ans.cal=ans.line=;

         pre_chuli();

         printf("%d\n",Fast_matrax(n));

     }

     fclose(stdin);fclose(stdout);

     return ;

 }