fork download
copy 
  1. #include <assert.h>
  2. #include <stdlib.h>
  3. #include <stdio.h>
  4.  
  5. struct matrix {
  6.     int rows, cols;
  7.     long *array;
  8. };
  9.  
  10. long& m_el(const matrix& m, int row, int col)
  11. {
  12.     return m.array[m.cols * row + col];
  13. }
  14.  
  15. void m_init(matrix& m, int rows, int cols)
  16. {
  17.     m.rows = rows;
  18.     m.cols = cols;
  19.     m.array = (long*)malloc(sizeof(long) * rows * cols);
  20. }
  21.  
  22. void m_copy(matrix& dest, matrix& src)
  23. {
  24.     int i;
  25.     for (i = 0; i < src.rows * src.cols; ++i)
  26.         dest.array[i] = src.array[i];
  27. }
  28.  
  29. matrix *m_genn(int n)
  30. {
  31.     int x, y;
  32.     matrix *m = (matrix*)malloc(sizeof(matrix));
  33.     m_init(*m, n, n);
  34.     for (y = 0; y < n; ++y) {
  35.         for (x = 0; x < n; ++x) {
  36.             if (x == y)
  37.                 m_el(*m, y, x) = 1;
  38.             else
  39.                 m_el(*m, y, x) = 0;
  40.         }
  41.     }
  42.     return m;
  43. }
  44.  
  45. long m_mul_rc(matrix& src1, matrix& src2, int row, int col)
  46. {
  47.     int i;
  48.     long sum = 0;
  49.     for (i = 0; i < src1.cols; ++i)
  50.         sum += m_el(src1, row, i) * m_el(src2, i, col);
  51.     return sum;
  52. }
  53.  
  54. void m_mul(matrix& dest, matrix& src1, matrix& src2)
  55. {
  56.     assert(src1.cols == src2.rows && src1.rows == dest.rows &&
  57.             src2.cols == dest.cols);
  58.     int x, y;
  59.     for (y = 0; y < dest.rows; ++y) {
  60.         for (x = 0; x < dest.cols; ++x)
  61.             m_el(dest, y, x) = m_mul_rc(src1, src2, y, x) % 100007;
  62.     }
  63. }
  64.  
  65. matrix *m_pow(matrix& src, matrix& one, int pow)
  66. {
  67.     if (pow == 0) {
  68.         matrix *res = (matrix*)malloc(sizeof(matrix));
  69.         m_init(*res, src.rows, src.cols);
  70.         m_copy(*res, one);
  71.         return res;
  72.     } else if (pow % 2 == 0) {
  73.         matrix *ir = m_pow(src, one, pow / 2);
  74.         matrix *r = (matrix*)malloc(sizeof(matrix));
  75.         m_init(*r, src.rows, src.cols);
  76.         m_mul(*r, *ir, *ir);
  77.         free(ir->array);
  78.         free(ir);
  79.         return r;
  80.     } else {
  81.         matrix *ir = m_pow(src, one, pow / 2);
  82.         matrix *r1 = (matrix*)malloc(sizeof(matrix));
  83.         matrix *r2 = (matrix*)malloc(sizeof(matrix));
  84.         m_init(*r1, src.rows, src.cols);
  85.         m_init(*r2, src.rows, src.cols);
  86.  
  87.         m_mul(*r1, *ir, *ir);
  88.         m_mul(*r2, *r1, src);
  89.         free(ir->array);
  90.         free(ir);
  91.         free(r1->array);
  92.         free(r1);
  93.         return r2;
  94.     }
  95. }
  96.  
  97. int main()
  98. {
  99.     int i, tnum;
  100.     scanf("%d", &tnum);
  101.  
  102.     for (i = 0; i < tnum; ++i) {
  103.         matrix ini, trs;
  104.         int n, m, j, k;
  105.         scanf("%d%d", &n, &m);
  106.         m_init(ini, n, 1);
  107.         m_init(trs, n, n);
  108.  
  109.         for (j = 0; j < n; ++j) {
  110.             for (k = 0; k < n; ++k) {
  111.                 int p;
  112.                 scanf("%d", &p);
  113.                 m_el(trs, j, k) = p;
  114.             }
  115.         }
  116.         for (j = 0; j < n; ++j) {
  117.             int p;
  118.             scanf("%d", &p);
  119.             m_el(ini, 0, j) = p;
  120.         }
  121.  
  122.         matrix *nm = m_pow(trs, *m_genn(n), m);
  123.         matrix res;
  124.         m_init(res, n, 1);
  125.         m_mul(res, *nm, ini);
  126.  
  127.         printf("Case #%d: ", i + 1);
  128.         for (j = 0; j < n; ++j)
  129.             printf("%ld%c", m_el(res, j, 0),  j + 1 == n ? '\n' : ' ');
  130.     }
  131.     return 0;
  132. }
Success #stdin #stdout 0s 5476KB
comments (?)
stdin
copy 
2
2 39
1 1
1 0
1 0
2 24
3 1
1 0
1 0
stdout
copy 
Case #1: 26994 41562
Case #2: 6860 73223
https://ideone.com/QiumMW
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!