poj 3233 Matrix Power Series

Matrix Power Series Time Limit: 3000MSMemory Limit: 131072KTotal Submissions: 3112Accepted: 1163

Description

Given a n × n matrix A and a positive integer k, find the sum S = A + A² + A³ + … + A^k.

Input

The input contains exactly one test case. The first line of input contains three positive integers n (n ≤ 30), k (k ≤ 10⁹) and m (m < 10⁴). Then follow n lines each containing n nonnegative integers below 32,768, giving A’s elements in row-major order.

Output

Output the elements of S modulo m in the same way as A is given.

Sample Input

2 2 4 0 1 1 1

Sample Output

1 2 2 3

Source

POJ Monthly--2007.06.03, Huang, Jinsong

[Submit]   [Go Back]   [Status]   [Discuss]

 

// 5138440 11410 3233 Wrong Answer   C++ 1597B 2009-05-12 11:28:50  // 5138462 11410 3233 Accepted 876K 125MS C++ 1718B 2009-05-12 11:34:08  // Given a n × n matrix A and a positive integer k, find the sum S = A + A2 + A3 + … + Ak. #include  < iostream > #define  MAX 33 using   namespace  std; typedef  struct  node {      int  matirx[MAX][MAX]; }Matrix; Matrix a,sa,unit; int  n,k,m; void  Init() {      int  i,j;      for (i = 0 ;i < n;i ++ )          for (j = 0 ;j < n;j ++ )         {             scanf( " %d " , & a.matirx[i][j]);             a.matirx[i][j] %= m;    // 初始化要先%m             unit.matirx[i][j] = (i == j);   // 如果i==j那么矩阵中此值就是1,否则为0,就是主对角线是1的单位矩阵         } } Matrix Add(Matrix a,Matrix b)   // 矩阵加法 {     Matrix c;      int  i,j;      for (i = 0 ;i < n;i ++ )          for (j = 0 ;j < n;j ++ )         {             c.matirx[i][j] = a.matirx[i][j] + b.matirx[i][j];             c.matirx[i][j] %= m;    // 加的时候也要%m         }      return  c; } Matrix Mul(Matrix a,Matrix b)   // 矩阵乘法 {     Matrix c;      int  i,j,k;      for (i = 0 ;i < n;i ++ )          for (j = 0 ;j < n;j ++ )         {             c.matirx[i][j] = 0 ;   // 初始化矩阵c              for (k = 0 ;k < n;k ++ )                 c.matirx[i][j] += a.matirx[i][k] * b.matirx[k][j];             c.matirx[i][j] %= m;   // 计算乘法的时候也要%m         }      return  c; } Matrix Cal( int  exp)    // 矩阵幂 {     Matrix p,q;     p = a;   // p是初始矩阵     q = unit;   // q是单位矩阵      while (exp != 1 )     {          if (exp & 1 )   // 要求得幂是奇数         {             exp -- ;             q = Mul(p,q);         }           else      // 要求的幂是偶数         {             exp >>= 1 ;   // 相当于除2             p = Mul(p,p);         }     }     p = Mul(p,q);      return  p; } Matrix MatrixSum( int  k) {      if (k == 1 )   // 做到最底层就将矩阵a返回就好          return  a;     Matrix temp,tnow;     temp = MatrixSum(k / 2 );      if (k & 1 )   // 如果k是奇数     {         tnow = Cal(k / 2 + 1 );         temp = Add(temp,Mul(temp,tnow));         temp = Add(tnow,temp);     }        else      // 如果k是偶数     {         tnow = Cal(k / 2 );         temp = Add(temp,Mul(temp,tnow));     }      return  temp; } int  main() {      int  i,j;      while (scanf( " %d%d%d " , & n, & k, & m) != EOF)     {         Init();         sa = MatrixSum(k);          for (i = 0 ;i < n;i ++ )         {              for (j = 0 ;j < n - 1 ;j ++ )             {                 printf( " %d  " ,sa.matirx[i][j] % m);             }             printf( " %d\n " ,sa.matirx[i][n - 1 ] % m);         }     }      return   0 ; }

转载于:https://www.cnblogs.com/forever4444/archive/2009/05/12/1454736.html

相关资源：数据结构—成绩单生成器