Задача
По заданной матрице 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 |
Код
|
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 |
#include <iostream> using namespace std; struct matrix { int mat[31][31]; }; long n, m; matrix E; //единичная матрица matrix mul(matrix A, matrix B) { matrix C; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) { C.mat[i][j] = 0; for (int v = 0; v < n; v++) C.mat[i][j] += A.mat[i][v] * B.mat[v][j] % m; } return C; } matrix sum(matrix A, matrix B) { for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) A.mat[i][j] += B.mat[i][j] % m; return A; } matrix power(matrix A, int k) { if (k == 1) return A; matrix B = power(A, k / 2); B = mul(B, B); if (k % 2 != 0) B = mul(B, A); return B; } matrix res(matrix A, int k) { if (k == 1) return A; if (k % 2 == 0) { matrix B = res(A, k / 2); return mul(sum(power(A, k / 2), E), B); } else { matrix B = res(A, k / 2); matrix C = power(A, (k + 1) / 2); return sum(C, mul(B, sum(C, E))); } } int main() { long long k; matrix A; cin >> n >> k >> m; for (int i = 0; i < n; i++) { E.mat[i][i] = 1; for (int j = 0; j < n; j++) cin >> A.mat[i][j]; } matrix ans = res(A, k); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (j != 0) cout << " "; cout << ans.mat[i][j] % m; } cout << "\n"; } return 0; } |
Решение
Для решения данной задачи опишем матрицу как структуру и функциями зададим простейшие операции над матрицами — сложение и умножение. Результат обеих функций будем будем брать по модулю $m$, чтоб уменьшить числа, с которыми работаем.
Далее создадим функцию быстрого возведения в степень. $A^k$ представим как $\left(A^2\right)^\frac{k}{2}$ при четном $k$ и $A × \left(A^2\right)^{\frac{k — 1}{2}}$ в противном случае. Такой алгоритм позволяет значительно уменьшить количество умножений.
И, наконец, последняя функция. Тут все зависит от показателя степени. Если он равен единице, ответом будет исходная матрица. Если же нет, функция становится рекурсивной и с помощью всех остальных описанных ранее функций нам удается получить искомую сумму.
Все, что еще необходимо сделать — вывести результат по модулю $m$.
Замечание
Тесты на e-olymp требуют отсутствия пробела после последнего столбца.