e-olymp 1485. Серия степеней матриц

Задача

По заданной матрице A размера n×n и положительному целому значению $k$ вычислить сумму $S = A + A^2+ A^3 + … + A^k.$

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

Первая строка содержит три положительных целых числа $n (n ≤ 30)$, $k (k ≤ 10^9)$ и $m (m < 10^4)$. Каждая из следующих $n$ строк содержит $n$ неотрицательных целых чисел меньших $32768$, задающих элементы матрицы $A$ в порядке возрастания строк.

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

Вывести элементы матрицы $S$ по модулю $m$ в таком же виде как и входная матрица $A$.

Тесты

Ввод Вывод
1 2 2 4
0 1
1 1
1 2
2 3
2 4 7 2
3 5 12
10 8 9
2 16 7
1 0 0 0
0 1 0 0
1 1 0 0
0 1 0 0
3 5 10 78
7 6 0 1 6
12 9 1 1 8
1 1 3 1 9
8 5 34 1 7
5 5 5 5 5
2 67 36 32 48
2 6 10 49 65
67 14 58 4 29
64 54 33 45 46
41 4 50 8 55
4 3 2 4
3 3 3
3 3 3
3 3 3
2 2 2
2 2 2
2 2 2
5 5 100 1000
1846 4675 8090 4539 1234
4567 7453 9564 6548 1111
5674 9876 5432 1010 1515
0 478 3 11 0
68303 7777 32767 14 8008
614 7 945 925 381
22 332 981 689 527
351 627 130 686 420
340 628 819 758 629
913 426 396 871 91

Код

Решение

Для решения данной задачи опишем матрицу как структуру и функциями зададим простейшие операции над матрицами — сложение и умножение. Результат обеих функций будем будем брать по модулю $m$, чтоб уменьшить числа, с которыми работаем.

Далее создадим функцию быстрого возведения в степень. $A^k$ представим как $\left(A^2\right)^\frac{k}{2}$ при четном  $k$ и $A × \left(A^2\right)^{\frac{k — 1}{2}}$ в противном случае. Такой алгоритм позволяет значительно уменьшить количество умножений.

И, наконец, последняя функция. Тут все зависит от показателя степени. Если он равен единице, ответом будет исходная матрица. Если же нет, функция становится рекурсивной и с помощью всех остальных описанных ранее функций нам удается получить искомую сумму.

Все, что еще необходимо сделать — вывести результат по модулю $m$.

Замечание

Тесты на e-olymp требуют отсутствия пробела после последнего столбца.

Ссылки

Условие задачи на e-olymp

Код задачи на Ideone

Related Images:

А712

Задача

Дана квадратная матрица [latex]A[/latex] порядка [latex]n[/latex]. Получить матрицы [latex]\frac{1}{2}(A+A^{*}) (1)[/latex] и [latex]\frac{1}{2}(A-A^{*}) (2)[/latex].

Тесты:

Ввод Вывод (1) Вывод (2)
3
1 2 3
2 4 6
1 4 8
1 2 2
2 4 5
2 5 8
0 0 1
0 0 1
-1 -1 0

Код:

Ссылка на ideone.

Сначала, вводим размер матрицы и саму матрицу, сразу же транспонируем ее. Теперь каждый элемент обычной матрицы прибавляем к транспонированному и отнимаем от транспонированного в последствии умножая на [latex]\frac{1}{2}[/latex]. Записываем это в две различные матрицы с результатом и выводим их на экран.

Код на Java

 

Related Images:

A393a

Задача. Даны натуральное число [latex]n[/latex], целочисленная квадратная матрица порядка [latex]n[/latex]. Получить [latex]{b}_{1}[/latex],…,[latex]{b}_{n}[/latex], где [latex]{b}_{i}[/latex] — это наименьшее из значений, элементов находящихся в начале i-й строки матрицы до элемента, принадлежащего главной диагонали, включительно.

4
4 3 2 1
4 3 2 1
4 3 2 1
4 3 2 1
4 3 2 1
Пройдено
4
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
1 1 1 1
Пройдено

Считываем матрицу и проходим в цикле по каждой строке ведя поиск минимального элемента, но есть одно «Но», из-за которого эта задача по интереснее чем просто задача о простом нахождении минимума: и это тот факт что поиск ведется под главной диагональю матрицы.
У всех элементов находящихся под главной диагональю матрицы, включительно, индекс строк больше или равен индексу столбцов заданной матрицы. Учтем это при составлении программы.
На этом все интересное заканчивается осталось только написать код с учетом вышеперечисленных особенностей задачи.

Проверить можно здесь: http://ideone.com/6yjlQQ

Related Images:

A405

Задача

Даны натуральное число [latex]n[/latex], действительная квадратная матрица порядка  [latex]n[/latex]. Построить последовательность [latex] b_1,..,b_n[/latex] из нулей и единиц, в которой [latex] b_i = 1[/latex] тогда и только тогда, когда в [latex]i[/latex] — строке  матрицы есть хотя бы один отрицательный элемент.

Тест

при  [latex]n = 3[/latex]

[latex]b_1[/latex] [latex]b_2[/latex] [latex]b_3[/latex] результат
0 0 0 0 1 0
0 -1 0
0 0 0

при [latex]n = 4[/latex]

[latex]b_1[/latex] [latex]b_2[/latex] [latex]b_3[/latex] [latex]b_4[/latex] результат
0 0 -1 0 1 1 0 1
0 -4 0 0
0 0 0 0
-8 0 0 0

при [latex]n=3[/latex]

[latex]b_1[/latex] [latex]b_2[/latex] [latex]b_3[/latex] результат
-0.75 0.98  4.67 1 0 1
4.89 0 3.75
-9.85 0 2.65

 

 

Ссылка на C++:http:http://ideone.com/KzTDgC

Ссылка на Java: http://ideone.com/EIZdZt

Решение:

Вводим квадратную матрицу [latex] z[n][n][/latex]  порядка  [latex]n[/latex].Далее в цикле описываем, что если :

то каждый элемент  [latex]b_i = 1[/latex], в противном случае  [latex]b_i = 0[/latex].Далее в input вводим количество элементов и соответствующие значения и получаем ответ.

Related Images: