eolymp-103. Симуляция процесса

Условие

Вам задан некоторый дискретный эволюционный процесс. В каждый момент времени состояние процесса описывается параметрами $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 \le T \le 10)$. Первая строка каждого теста содержит $2$ числа: $N$ $(1 \le N \le 100)$ — количество параметров и $M$ $(0 \le M \le 10^9)$ момент времени. Далее следуют $N$ строк, каждая из которых содержит $N$ целых чисел, разделённых пробелами. $j$-е число в $i$-й строке — $a_{ij}$ $(0 \le a_{ij} \le 10^9)$. Далее следует одна строка, содержащая $N$ целых чисел. $j$-е число в этой строке — $x_j^0$ $(0 \le x_j^0 \le 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

Код программы

Решение

Пусть $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

One thought on “eolymp-103. Симуляция процесса

  1. Хороший результат. Вы на первом месте первом месте по скорости.
    Зачел, но поправьте
    — знак меньше либо равно должен выглядеть как в учебнике математики;
    — сделайте все числа в LaTeX, а то два разных шрифта в разных местах выходят.

Добавить комментарий