HDU1575Tr A（矩阵相乘与快速幂）

时间：2023-03-08 19:42:42

Tr A hdu1575

就是一个快速幂的应用：

只要知道怎么求矩阵相乘！！（比赛就知道会超时，就是没想到快速幂！！！）

 #include<iostream>

 #include<stdio.h>

 #include<string.h>

 #include<algorithm>

 using namespace std;

 __int64 a[][],b[][],c[][];

 int n;

 int main()

 {

     int t,i,j,m,k,d;

     __int64 sum;

     scanf("%d",&t);

     while(t--)

     {

         scanf("%d%d",&n,&m);

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

             for(j=;j<n;j++)

             {scanf("%I64d",&a[i][j]);b[i][j]=a[i][j];}

         d=;

         while(m)

         {

             if(m%&&d==)//因为快速幂规定起始为1，则第一次就来要分开考虑！！

             {

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

                     for(j=;j<n;j++)

                         a[i][j]=b[i][j];

                 d=;

             }

             else if(m%)

             {

                 memset(c,,sizeof(c));

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

                     for(j=;j<n;j++)

                     for(k=;k<n;k++)

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

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

                     for(j=;j<n;j++)

                         a[i][j]=c[i][j];

             }

             m=m/;

             memset(c,,sizeof(c));

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

         for(j=;j<n;j++)

         for(k=;k<n;k++)

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

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

         for(j=;j<n;j++)

             b[i][j]=c[i][j];

         }

         sum=;

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

             sum+=a[i][i];

         printf("%I64d\n",sum%);

     }

     return ;

 }

附上快速幂的模板：

 __int64 power(__int64 p,__int64 n)  //反复平方法求(p^n)%mod

 {

     __int64 sq=;

     while(n>)

     {

         if(n%)

             sq=(sq*p)%mod;

         n/=;

         p=p*p%mod;

     }

     return sq;

 }

相关文章