HDU 1575(裸矩阵快速幂)

时间：2024-10-25 08:34:08

emmmmm..就是矩阵快速幂，直接附代码：

 #include <cstdio>

 using namespace std;

 const int maxn = ;

 const int mod = ;

 struct Matrix

 {

     int m[maxn][maxn];

 }ans,res;

 int n;

 Matrix mul(Matrix a,Matrix b)

 {

     Matrix tmp;

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

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

             tmp.m[i][j] = ;

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

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

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

                 tmp.m[i][j] += ((a.m[i][k] % mod)*(b.m[k][j] % mod))%mod;

     return tmp;

 }

 void quickpow(int N)

 {

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

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

             if(i == j)  ans.m[i][j] = ;

             else ans.m[i][j] = ;

     while(N)

     {

         if(N&) ans = mul(ans,res);

         res = mul(res,res);

         N = N >>;

     }

 }

 int main()

 {

     int t,k,wu;

     scanf("%d",&t);

     while(t--)

     {

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

         wu = ;

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

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

                 scanf("%d",&res.m[i][j]);

         quickpow(k);

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

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

                 if(i == j)  wu += ans.m[i][j];

         printf("%d\n",wu%mod);

     }

     return ;

 }

相关文章