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

e-olymp 4439. Возведение в степень

Задача

Вычислить значение $a^b$.

Входные данные

Два натуральных числа $a$ и $b$.

Выходные данные

Выведите значение $a^b$, если известно что оно не превосходит $10^{18}$.

Тесты

ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
 1 1 100 1
 2 2 10 1024
 3 3 7 2187
 4 8 9 134217728
 5 10 10 10000000000
 6 100 9 1000000000000000000

Код

Решение

Для решения задачи создадим функцию «pow()», заметим, что для любого числа $a$ и чётного числа $b$ выполнимо очевидное тождество (следующее из ассоциативности операции умножения):
$$a^b = \left(a^2\right)^{\frac{b}{2}}= \left(a\cdot a\right)^{\frac{b}{2}}$$
Оно и является основным в методе бинарного возведения в степень. Действительно, для чётного $b$ мы показали, как, потратив всего одну операцию умножения, можно свести задачу к вдвое меньшей степени.
Осталось понять, что делать, если степень b нечётна. Здесь мы поступаем очень просто: перейдём к степени b-1, которая будет уже чётной:
$$a^b = a^{b-1} \cdot a$$
Итак, мы фактически нашли рекуррентную формулу: от степени $b$ мы переходим, если она чётна, к $\frac{b}{2}$, а иначе — к $b-1$.

Примечание

Задача требует использование быстрого алгоритма, так как прямое умножение $b$ раз для возведение в $b$-ю слишком медленно, из-за большого количества перемножений. Алгоритм быстрого возведения в степень — это предназначенный для возведения числа в натуральную степень за меньшее число умножений, чем это требуется в определении степени.

Ссылки

Условие задачи на e-olymp
Код на Ideone
Засчитанное решение на e-olymp

e-olymp 2814. Быстрое возведение в степень.

Задача

Быстрое возведение в степень

Быстрое возведение в степень

Очень часто возникает задача эффективного вычисления $x^{n}$ по данным $x$ и $n$, где $n$ — положительное целое число.
Предположим, например, что необходимо вычислить $x^{16}$. Можно просто начать с $x$ и 15 раз умножить его на $x$. Но тот же ответ можно получить всего за четыре умножения, если несколько раз возвести в квадрат получающийся результат, последовательно вычисляя $x^{2}$, $x^{4}$, $x^{8}$, $x^{16}$.
Эта же идея, в целом, применима к любому значению $n$ следующим образом. Запишем $n$ в виде числа в двоичной системе счисления (убирая нули слева). Затем заменим каждую «1» парой символов SX, а каждый «0» — символом S и вычеркнем крайнюю слева пару символов SX. Результат представляет собой правило вычисления $x^{n}$, в котором «S» трактуется как операция возведения в квадрат, а «X» — как операция умножения на $x$. Например, $n = 23$ имеет двоичное представление $10111$. Таким образом, мы формируем последовательность SXSSXSXSX, из которой удаляем начальную пару SX для получения окончательного правила SSXSXSX. Это правило гласит, что необходимо «возвести в квадрат, возвести в квадрат, умножить на $x$, возвести в квадрат, умножить на $x$, возвести в квадрат и умножить на $x$», т.е. последовательно вычислить значения $x^{2}$, $x^{4}$, $x^{5}$, $x^{10}$, $x^{11}$, $x^{22}$, $x^{23}$.

Вам нужно для заданного n сформулировать соответствующее правило быстрого возведения числа $x$ в степень $x^{n}$

Входные данные

Одно натуральное число $n$, не превышающее $2 \cdot 10^{9}$.

Выходные данные

Выведите строку для правила возведения числа $x$ в степень $n$ для получения $x^{n}$.

Тесты

# Входные данные Выходные данные
1 23 SSXSXSX
2 1
3 16 SSSS
4 1000000 SXSXSXSSXSSSSSXSSSXSSSSSS
5 2018 SXSXSXSXSXSSSSXS

Решение

С помощью первого цикла while в переменную $k$ записываем перевернутый двоичный код числа $n$. Переменную $c$ используем как счётчик кол-ва бит в $n$. Во втором цикле while выводим S или SX если правый бит $0$ или $1$ соответственно, теряя при это последнюю $1$ как и сказано по условию задачи.

Условие задачи можно найти на e-olymp
Код решения — ideone

Ю3.20

Задача: Для заданных [latex]a[/latex] и [latex]p[/latex] вычислить [latex]x = \sqrt[p]{a}[/latex] по рекуррентному соотношению Ньютона: 

[latex]x_{n+1}=\frac{1}{p}*\left[(p-1)x_{n}+\frac{a}{x_{n}^{p-1}}\right][/latex]  [latex]x_{0} = a[/latex]

Сколько итераций надо выполнить, чтобы для достижения заданной погрешности [latex]\varepsilon[/latex] выполнялось соотношение:

[latex]\left|x_{n+1}-x_{n}\leq\varepsilon\right|[/latex]?

Тесты:

[latex]a[/latex] [latex]p[/latex] Значение корня [latex]x[/latex] Значение корня [latex]x[/latex], подсчитанного с помощью соотношения Количество итераций
57 5  2.24479 2.24479  18
16 2 4 4 5
230 2  15.1658  15.1658 7
9 3  2.08008 2.08008  7

Код на С++: 

Код на Java:

 

 

Решение: Для подсчёта значения корня с помощью рекуррентного соотношения, я создал цикл, в котором организовал подсчёт значения таким образом, что пока разница значения корня x, подсчитанного с помощью функции pow, cо значением текущего корня xn,  подсчитанным с помощью соотношения, больше заданной погрешности eps, то, записывая текущее значение в переменную x_prev, подсчитываю новое значение корня. В зависимости от заданной погрешности, программа считает результат и выводит его на экран вместе с кол-вом итераций.

UPD: По предложению Игоря Евгеньевича добавил быстрое возведение в целую степень.

Решение UPD: Чтобы построить алгоритм быстрого возведения в степень, необходимо рассмотреть две ситуации:

  1. Когда степень чётна;
  2. Когда степень не чётна;

Ситуация 1 : Проведя несложный анализ  можно заметить, что [latex]{a}^{p}[/latex] можно представить в виде

[latex](a^{\frac{p}{2}})^{2}[/latex].

Ситуация 2: В этой ситуации необходимо перейти в степень [latex]p-1[/latex], которая является чётной.

[latex]a^{p}=a^{p-1} * a[/latex]

И в результате получим алгоритм, который работает за [latex]O(\log n)[/latex].

 

Проверить правильность работы программы можно здесь (UPD):  http://ideone.com/VBLGKO