poj-3233 Matrix Power(构造矩阵+矩阵快速幂)

深藏阁楼爱情的钟 2022-06-05 12:15 296阅读 0赞

Matrix Power Series














Time Limit: 3000MS   Memory Limit: 131072K
Total Submissions: 24823   Accepted: 10304

Description

Given a n × n matrix A and a positive integer k, find the sum S = A + A2 + A3 + … + Ak.

Input

The input contains exactly one test case. The first line of input contains three positive integers n (n ≤ 30), k (k ≤ 109) and m (m < 104). 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

  1. 2 2 4
  2. 0 1
  3. 1 1

Sample Output

  1. 1 2
  2. 2 3

Source

POJ Monthly—2007.06.03, Huang, Jinsong

思路:常规写无疑会超时,我们会发现S(k)=A(S(k-1))+A

所以可以构造[S(n), E]=[S(n-1), E]*[A, 0 ; A, E]=[S(1), E]*[A, 0 ; A, E]^(n-1)

用矩阵快速幂求出[A, 0 ; A, E]^(n-1)即可;

  1. #include<cstdio>
  2. using namespace std;
  3. int k, n, m;
  4. typedef struct Matrix{
  5. int a[100][100];
  6. }Matrix;
  7. Matrix A, S;
  8. Matrix mul(Matrix x, Matrix y, int row, int col)
  9. {
  10. Matrix c;
  11. for(int i=1; i<=row; i++)
  12. for(int j=1; j<=col; j++)
  13. {
  14. c.a[i][j]=0;
  15. for(int k=1; k<=col; k++)
  16. c.a[i][j]=(c.a[i][j]%m + (x.a[i][k]%m)*(y.a[k][j]%m))%m;
  17. }
  18. return c;
  19. }
  20. Matrix pow(Matrix x, int t)
  21. {
  22. Matrix c;
  23. for(int i=1; i<=2*n; i++)
  24. for(int j=1; j<=2*n; j++)
  25. if(i==j)
  26. c.a[i][j]=1;
  27. else
  28. c.a[i][j]=0;
  29. while(t)
  30. {
  31. if(t&1)
  32. {
  33. c=mul(c, x, 2*n, 2*n);
  34. }
  35. x=mul(x, x, 2*n, 2*n);
  36. t>>=1;
  37. }
  38. return c;
  39. }
  40. int main(){
  41. scanf("%d%d%d", &n, &k, &m);
  42. for(int i=1; i<=n; i++)
  43. {
  44. for(int j=1; j<=n; j++)
  45. {
  46. scanf("%d", &A.a[i][j]);
  47. S.a[i][j]=A.a[i][j];
  48. A.a[n+i][j]=A.a[i][j];
  49. A.a[i][n+j]=0;
  50. i==j? A.a[n+i][n+j]=1:A.a[n+i][n+j]=0;
  51. i==j? S.a[i][n+j]=1:S.a[i][n+j]=0;
  52. }
  53. }
  54. A=pow(A, k-1);
  55. S=mul(S, A, n, 2*n);
  56. for(int i=1; i<=n; i++)
  57. {
  58. for(int j=1; j<n; j++)
  59. printf("%d ", S.a[i][j]);
  60. printf("%d\n", S.a[i][n]);
  61. }
  62. return 0;
  63. }

发表评论

表情:
评论列表 (有 0 条评论,296人围观)

还没有评论,来说两句吧...

相关阅读