Условие
Вам задан некоторый дискретный эволюционный процесс. В каждый момент времени состояние процесса описывается параметрами $x_{1},\dotsc, x_{n}$. В каждый момент времени эволюция описывается следующей системой линейных уравнений:
$
\begin{cases}
x^{i+1}_1 = a_{11}x^i_1 + \dotsc + a_{1n}x^i_n \\
\text{ }\\
\dotsc \\
\text{ } \\
x^{i+1}_n = a_{n1}x^i_1 + \dotsc + a_{nn}x^i_n
\end{cases}
$
Найдите состояние процесса в момент времени $M$. Каждый параметр должен быть посчитан по модулю $100007$.
Входные данные
Первая строка ввода содержит количество тестов $T$ $(1 \leqslant T \leqslant 10)$. Первая строка каждого теста содержит $2$ числа: $N$ $(1 \leqslant N \leqslant 100)$ — количество параметров и $M$ $(0 \leqslant M \leqslant 10^9)$ момент времени. Далее следуют $N$ строк, каждая из которых содержит $N$ целых чисел, разделённых пробелами. $j$-е число в $i$-й строке — $a_{ij}$ $(0 \leqslant a_{ij} \leqslant 10^9)$. Далее следует одна строка, содержащая $N$ целых чисел. $j$-е число в этой строке — $x_j^0$ $(0 \leqslant x_j^0 \leqslant 10^9)$ .
Выходные данные
Выведите $T$ строк вида «Case #$A$: $x^M_1, \dotsc, x^M_n$», где $A$ — номер теста (начиная с $1$), $x^M_1, \dotsc, x^M_n$ – искомые параметры для данного теста.
Тесты
|
Входные данные
|
Выходные данные
|
2
1 5
2
1
2 7
14 26
32 45
534 623
|
Case #1: 32
Case #2: 62813 87846
|
|
2
2 39
1 1
1 0
1 0
2 24
3 1
1 0
1 0
|
Case #1: 26994 41562
Case #2: 6860 73223
|
Код программы
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 |
#include <assert.h> #include <stdlib.h> #include <stdio.h> struct matrix { int rows, cols; long *array; }; long& m_el(const matrix& m, int row, int col) { return m.array[m.cols * row + col]; } void m_init(matrix& m, int rows, int cols) { m.rows = rows; m.cols = cols; m.array = (long*)malloc(sizeof(long) * rows * cols); } void m_copy(matrix& dest, matrix& src) { int i; for (i = 0; i < src.rows * src.cols; ++i) dest.array[i] = src.array[i]; } matrix *m_genn(int n) { int x, y; matrix *m = (matrix*)malloc(sizeof(matrix)); m_init(*m, n, n); for (y = 0; y < n; ++y) { for (x = 0; x < n; ++x) { if (x == y) m_el(*m, y, x) = 1; else m_el(*m, y, x) = 0; } } return m; } long m_mul_rc(matrix& src1, matrix& src2, int row, int col) { int i; long sum = 0; for (i = 0; i < src1.cols; ++i) sum += m_el(src1, row, i) * m_el(src2, i, col); return sum; } void m_mul(matrix& dest, matrix& src1, matrix& src2) { assert(src1.cols == src2.rows && src1.rows == dest.rows && src2.cols == dest.cols); int x, y; for (y = 0; y < dest.rows; ++y) { for (x = 0; x < dest.cols; ++x) m_el(dest, y, x) = m_mul_rc(src1, src2, y, x) % 100007; } } matrix *m_pow(matrix& src, matrix& one, int pow) { if (pow == 0) { matrix *res = (matrix*)malloc(sizeof(matrix)); m_init(*res, src.rows, src.cols); m_copy(*res, one); return res; } else if (pow % 2 == 0) { matrix *ir = m_pow(src, one, pow / 2); matrix *r = (matrix*)malloc(sizeof(matrix)); m_init(*r, src.rows, src.cols); m_mul(*r, *ir, *ir); free(ir->array); free(ir); return r; } else { matrix *ir = m_pow(src, one, pow / 2); matrix *r1 = (matrix*)malloc(sizeof(matrix)); matrix *r2 = (matrix*)malloc(sizeof(matrix)); m_init(*r1, src.rows, src.cols); m_init(*r2, src.rows, src.cols); m_mul(*r1, *ir, *ir); m_mul(*r2, *r1, src); free(ir->array); free(ir); free(r1->array); free(r1); return r2; } } int main() { int i, tnum; scanf("%d", &tnum); for (i = 0; i < tnum; ++i) { matrix ini, trs; int n, m, j, k; scanf("%d%d", &n, &m); m_init(ini, n, 1); m_init(trs, n, n); for (j = 0; j < n; ++j) { for (k = 0; k < n; ++k) { int p; scanf("%d", &p); m_el(trs, j, k) = p; } } for (j = 0; j < n; ++j) { int p; scanf("%d", &p); m_el(ini, 0, j) = p; } matrix *nm = m_pow(trs, *m_genn(n), m); matrix res; m_init(res, n, 1); m_mul(res, *nm, ini); printf("Case #%d: ", i + 1); for (j = 0; j < n; ++j) printf("%ld%c", m_el(res, j, 0), j + 1 == n ? '\n' : ' '); } return 0; } |
Решение
Пусть $V^M = [x^M_1, x^M_2, \dotsc, x^M_n]^T$, $V^0$ — исходное состояние процесса и $A = \| a_{ij} \|$, где $i = \overline{1,n}$, $j = \overline{1,n}$.
Можно заметить, что $\forall k:\text{ }V^{k+1} = AV^k$. Отсюда, в силу ассоциативности умножения матриц, заключаем, что $V^k = A^kV^0$.
Для возведения матрицы $A$ в степень $M$ воспользуемся алгоритмом быстрого возведения в степень, работающим по следующей схеме:
$x^n =\begin{cases}
1\text{, если $n$ = 0} \\
(x^2)^\frac{n}{2}\text{, если $n$ чётно} \\
x\cdot(x^2)^\frac{n-1}{2}\text{, если $n$ нечётно}
\end{cases}
$
Ссылки
Условие задачи на eolymp.com
Решение задачи на ideone.com
Например, замостить прямоугольник $2 × 3$ можно только тремя различными способами. Поскольку ответ может быть достаточно большим, искомое количество способов следует вычислять по модулю $10^6$.
