e-olymp 8651. Браслети (Bangles)

14/06/2019 by Руслан Масальский

Задача взята з сайту e-olymp

Шпигунам-конкурентам вдалося потрапити на склад запасних частин фірми «Magic & Stupidity», яка виготовляла магічні браслети. Стало зрозуміло, що всі браслети складалися з чотирьох різних деталей, кожна з яких мала на кінцях замки різних типів (розрізнялися за номерами). Вони з’єднувалися по колу, причому у сусідніх частин замки повинні мати однаковий номер. Знайшлося $N$ різних типів замків (позначимо їх номерами від $1$ до $N$) і $М$ типів деталей, які визначаються парою номерів замків (порядок несуттєвий). Напишіть програму, яка б підраховувала скільки існує різних наборів з чотирьох деталей для виготовлення браслетів фірмою «Magic & Stupidity».

Вхідні дані

Програма читає з першого рядка числа $N$ (кількість типів замків) та $M$ (кількість типів деталей). ($4 \leqslant N \leqslant 300$). У $M$ наступних рядках наведені параметри деталей (пара номерів замків). Всі пари різні.

Вихідні дані

Програма визначає кількість варіантів браслетів.

Тести

№	Inputs	Outputs
1	5 7 1 3 1 4 2 4 2 5 3 4 3 5 4 5	2
2	4 4 1 2 2 3 3 4 1 4	1
3	5 5 1 2 2 3 3 5 1 4 1 5	1

Код

#include <iostream>
using namespace std;
typedef long long ll;
const ll INF = 3e2+5;
ll arr[INF][INF];
void power(ll n){
    ll arr1[n][n];
    for(int i  = 0 ; i < n ; i++){
        for(int j = 0 ; j < n; j++){
            arr1[i][j]=0;
            for(int k = 0 ; k < n ; k ++){
                arr1[i][j]+=arr[i][k]* arr[k][j];
            }
            
        }
    }
    for(int i  = 0 ; i < n ; i++){
        for(int j = 0 ; j < n; j++){
            arr[i][j]=arr1[i][j];
        }
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n,m ;
    cin>>n>>m;
    ll a,b;
    for(int i = 0 ; i < m ; i++){
        cin>>a>>b;
        a--;
        b--;
        if(a!=b){
            arr[a][b]++;
            arr[b][a]++;    
        }
    }
    power(n);
    ll to_del[n];
    for(int i = 0 ; i < n; i++){
        to_del[i]=0;
        for(int j = 0 ; j < n; j++){
            if(i==j){
                arr[i][i] = 0;
            }else{
                to_del[i]+=arr[i][j];
            }
        }
    }
    power(n);
    ll answer =0;
    for(int i = 0 ; i < n ; i++){
        answer +=arr[i][i]-to_del[i];
    }
    cout<<answer/8;
    return 0;
}

#include <iostream>

using namespace std;

typedef long long ll;

const ll INF = 3e2+5;

ll arr[INF][INF];

void power(ll n){

ll arr1[n][n];

for(int i = 0 ; i < n ; i++){

for(int j = 0 ; j < n; j++){

arr1[i][j]=0;

for(int k = 0 ; k < n ; k ++){

arr1[i][j]+=arr[i][k]* arr[k][j];

}

for(int i = 0 ; i < n ; i++){

for(int j = 0 ; j < n; j++){

arr[i][j]=arr1[i][j];

}

int main() {

ios_base::sync_with_stdio(0);

cin.tie(0);

int n,m ;

cin>>n>>m;

ll a,b;

for(int i = 0 ; i < m ; i++){

cin>>a>>b;

a--;

b--;

if(a!=b){

arr[a][b]++;

arr[b][a]++;

}

power(n);

ll to_del[n];

for(int i = 0 ; i < n; i++){

to_del[i]=0;

for(int j = 0 ; j < n; j++){

if(i==j){

arr[i][i] = 0;

}else{

to_del[i]+=arr[i][j];

}

power(n);

ll answer =0;

for(int i = 0 ; i < n ; i++){

answer +=arr[i][i]-to_del[i];

}

cout<<answer/8;

return 0;

}

Рішення

Зробимо ізоморфний перехід в графи, а саме можна помітити, що визначивши типи запків як вершини матимемо зв’язки між типами, як існуючий елемент браслета, тобто пара $(1, 2)$ насправді задає зв’язок між першим і другим типом. Маэмо граф, залишилось знайти кількість простих циклів завдовшки у чотири ребра (чотири вершини).
Построївши матрицю суміжності ми на справді побудували матрицю де arr[i][j] містить кількість способів дійти від вершини $i$ до вершини $j$ за один хід.
Нехай за х ходів ми потрапили з вершини $i$ у вершину $k$ рівно $a$ способами, а з вершини $k$ у вершину $j$ рівно $b$ способами. Тоді за $2x$ ходів ми можемо потрапити з вершини $i$ у вершину $j$ через вершину $k$ рівно $ab$ способами, що насправді еквівалентно возведенню матриці суміжності у степінь, яка дорівнює кількості ходів
Тепер за два перемноження отримаємо матрицю де arr[i][j] містить кількість способів дійти від вершини $i$ до вершини $j$ за 4 ходи. Сумма елементів на головній діагоналі майже дає нам потрібний результат. Нам треба відняти ходи такого типу 1-2-1-2-1 та 1-2-3-2-1. Щоб відняти ходи першого типу після першого перемноження поставимо на головній діагоналі нулі, що означатиме що ми не можемо у другому ході повернутися у ту вершину з якої прибули. Для другого типу треба помітити, що ми йдемо по тому шляху, по якому вже йшли тобто якщо мі за два ходи дійшли до певної вершини $a$ способами, то повертаючись назад отримаємо $2a$ способів, але з них рівно $a$ нам не підходять, тому після другого перемноження с діагоналі видаляємо сумму на ряді на моменті коли було зроблено усього $2$ ходи, звісно не враховуючи елементи на головній діагоналі. Ми будували неорієнтований граф тому сумму на діагоналі треба поділити на $2,$ а ще в наших циклах по $4$ вершини, тому треба ще поділити на 4.

Посилання

ideone
e-olymp

Related Images:

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

26/01/2019 by Инна Литвиненко

Задача

По заданной матрице 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

Код

#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;
}

#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 требуют отсутствия пробела после последнего столбца.

Ссылки

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

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

Related Images:

A708

17/05/2015 by Фесенко Катерина Володимирівна

Задача

Даны квадратная матрица [latex]A[/latex] порядка [latex]m[/latex], натуральное число [latex]n[/latex]. Получить матрицу [latex]E+A+A^2+A^3+\dots+A^n,[/latex] где [latex]E[/latex] — единичная матрица порядка [latex]m[/latex].

Тесты

m, n

матрица А

результат

3 3

3 2 1

5 7 3

9 7 3

359 358 158

1028 1047 460

1156 1162 513

2 2

6 7

12 54

127 427

732 3055

Код на языке С++:

#include <iostream>
using namespace std;
 
int main() {
	int n, m;
	cin >> m >> n;
	double a[m][m]; //Исходная матрица
	double b[m][m]; //Вспомогательная матрица
	double c[m][m]; //Матрица в степени n
	double ans[m][m];//Результирующая матрица
	for(int i = 0; i < m; i++){
		for(int j = 0; j < m; j++){
			a[i][j] = b[i][j] = c[i][j] = ans[i][j] = 0; //Очистка памяти
		}
	}
	for(int i = 0; i < m; i++){
		for(int j = 0; j < m; j++){
			cin >> a[i][j];
			c[i][j] = b[i][j] = ans[i][j] = a[i][j];
		}
	}
	for(int it = 1; it < n; it++){
		//Возводим матрицу в след. степень
		for(int i = 0; i < m; i++){
			for(int j = 0; j < m; j++){
				c[i][j] = 0;
				for(int k = 0; k < m; k++){
					c[i][j] += a[i][k]*b[k][j];
				}
			}
		}
		for(int i = 0; i < m; i++){
			for(int j = 0; j < m; j++){
				ans[i][j] += c[i][j]; //Добавляем к ответу
				b[i][j] = c[i][j]; //Заменяем вспомогательную матрицу
			}
		}
	}
	//Добавляем единичную матрицу
	for(int i = 0; i < m; i++){
		ans[i][i]++;
	}
	//Вывод результата
	for(int i = 0; i < m; i++){
		for(int j = 0; j < m; j++){
			cout << ans[i][j] << ' ';
		}
		cout << endl;
	}
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, m;

cin >> m >> n;

double a[m][m]; //Исходная матрица

double b[m][m]; //Вспомогательная матрица

double c[m][m]; //Матрица в степени n

double ans[m][m];//Результирующая матрица

for(int i = 0; i < m; i++){

for(int j = 0; j < m; j++){

a[i][j] = b[i][j] = c[i][j] = ans[i][j] = 0; //Очистка памяти

}

for(int i = 0; i < m; i++){

for(int j = 0; j < m; j++){

cin >> a[i][j];

c[i][j] = b[i][j] = ans[i][j] = a[i][j];

}

for(int it = 1; it < n; it++){

//Возводим матрицу в след. степень

for(int i = 0; i < m; i++){

for(int j = 0; j < m; j++){

c[i][j] = 0;

for(int k = 0; k < m; k++){

c[i][j] += a[i][k]*b[k][j];

}

for(int i = 0; i < m; i++){

for(int j = 0; j < m; j++){

ans[i][j] += c[i][j]; //Добавляем к ответу

b[i][j] = c[i][j]; //Заменяем вспомогательную матрицу

}

//Добавляем единичную матрицу

for(int i = 0; i < m; i++){

ans[i][i]++;

}

//Вывод результата

for(int i = 0; i < m; i++){

for(int j = 0; j < m; j++){

cout << ans[i][j] << ' ';

}

cout << endl;

}

return 0;

}

Ссылка на программу:http://ideone.com/3B9ti7

Код на языке Java:

import java.util.*;
import java.lang.*;
import java.io.*;
class Ideone {
	public static void main (String[] args) {
		Scanner sc = new Scanner (System.in);
		int n, m;
		m = sc.nextInt();
		n = sc.nextInt();
		double [][] a = new double [m][m];
		double [][] b = new double [m][m];
		double [][] c = new double [m][m];
		double [][] ans = new double [m][m];
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < m; j++) {
				a[i][j] = sc.nextDouble();
				c[i][j] = b[i][j] = ans[i][j] = a[i][j];
			}
		}
		for (int it = 1; it < n; it++) {
			for (int i = 0; i < m; i++) {
				for (int j = 0; j < m; j++) {
					c[i][j] = 0;
					for (int k = 0; k < m; k++) {
						c[i][j] += a[i][k] * b[k][j];
					}
				}
			}
			for (int i = 0; i < m; i++) {
				for (int j = 0; j < m; j++) {
					ans[i][j] += c[i][j];
					b[i][j] = c[i][j];
				}
			}
		}
		for (int i = 0; i < m; i++) {
			ans[i][i]++;
		}
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < m; j++) {
				System.out.print(ans[i][j] + " ");
			}
			System.out.println();
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone {

public static void main (String[] args) {

Scanner sc = new Scanner (System.in);

int n, m;

m = sc.nextInt();

n = sc.nextInt();

double [][] a = new double [m][m];

double [][] b = new double [m][m];

double [][] c = new double [m][m];

double [][] ans = new double [m][m];

for (int i = 0; i < m; i++) {

for (int j = 0; j < m; j++) {

a[i][j] = sc.nextDouble();

c[i][j] = b[i][j] = ans[i][j] = a[i][j];

}

for (int it = 1; it < n; it++) {

for (int i = 0; i < m; i++) {

for (int j = 0; j < m; j++) {

c[i][j] = 0;

for (int k = 0; k < m; k++) {

c[i][j] += a[i][k] * b[k][j];

}

for (int i = 0; i < m; i++) {

for (int j = 0; j < m; j++) {

ans[i][j] += c[i][j];

b[i][j] = c[i][j];

}

for (int i = 0; i < m; i++) {

ans[i][i]++;

}

for (int i = 0; i < m; i++) {

for (int j = 0; j < m; j++) {

System.out.print(ans[i][j] + " ");

}

System.out.println();

}

Ссылка на программу: http://ideone.com/hOFldD

Решение:

Заводим четыре матрицы: исходную, вспомогательную, матрицу в степени [latex]n[/latex] и результирующую; обнуляем все матрицы, тем самым очищаем память. Дальше возводим матрицу в степень [latex]n[/latex], добавляем к результирующей и заменяем вспомогательную матрицу. В завершении мы прибавим единичную матрицу к ответы и выведем его.

Related Images:

А706 Алгоритм быстрого возведения в степень

14/05/2015 by Осецимський Анатолій Вадимович

Степень

Входная матрица

Результирующая матрица

0	1
2	3

2	3
6	11

0	1
2	3

6	11
22	39

Пусть даны квадратная матрица [latex]A[/latex] порядка [latex]m[/latex] и натуральное число [latex]n[/latex]; требуется найти [latex]A^{n}[/latex]. Алгоритм, основанный на непосредственной применении формулы [latex]A^{n} = A*A*A…*A [/latex]([latex]n[/latex] сомножителей), слишком разорителен. Например, [latex]A^{4}[/latex] экономичнее вычислять как [latex]A^{2^{2}}[/latex]. Идея одного достаточно экономичного алгоритма вычисления [latex]A^{n}[/latex] заключается в следующем: если [latex]n = 2k[/latex], то [latex]A^{n} = (A^{2})^{k}[/latex]; если же [latex]n = 2k + 1[/latex], то [latex]A^{n} = (A^{2})^{k} * A[/latex]. Степень с показателем [latex]k[/latex] вычисляется с учетом этих же соображений. Итак, надо разделить [latex]n[/latex] на [latex]2[/latex] с остатком:[latex] n = 2k + l [/latex] [latex](0\le l\le 1[/latex]), потом это же проделать с [latex]k[/latex] и т.д. Эти действия приводят, как известно, к построению двоичной записи [latex]n[/latex]. Алгоритм, основанный на этой идее, состоит в том, что последовательно вычисляются [latex]A^{a_{0}}, A^{a_{1}*a_{0}}, …,A^{a_{l}*…*a_{0}}, a_{l}*…*a_{0}[/latex] — двоичная запись числа [latex]n[/latex]. Для этого вычисляется, цифра за цифрой, двоичная запись [latex]n[/latex] и, параллельно, степень за степенью,[latex]A^{(2^{0})}, A^{(2^{1})}, …[/latex] — каждая следующая степень получается из предыдущей возведением в квадрат. Подсчитывается произведение тех из вычисленных степеней, для которых соответствующая цифра двоичного представления равна 1. Например, запись [latex]9[/latex] в двоичной системе есть [latex]1001[/latex][latex](9 = 1*8 + 0*4 + 0*2 + 1)[/latex]; для вычисления [latex]A^{9}[/latex] достаточно найти [latex]A^{2},A^{4},A^{8},[/latex]([latex]3[/latex] умножения), а затем определить [latex]A*A^{8},[/latex] ([latex]1[/latex] умножение).

Преимущество этого алгоритма в сравнении с простейшим состоит в том, что простейший алгоритм требует числа умножений, растущего как линейная функция от [latex]n[/latex], а здесь число умножений грубо говоря, пропорционально количеству цифр числа [latex]n[/latex] или двоичному логарифму [latex]n[/latex]. Это преимущество весьма ощутимо при работе с матрицами (из-за трудоемкости каждого умножения), хотя, разумеется, этот алгоритм может быть использован и для вычисления степени любого числа.

Написать программу, реализующую предположенный алгоритм.

Суть алгоритма была описана в задании. Реализация была через свою структуру данных, такую как матрица. В ней мы определили умножение и присваивание, для удобства. Есть несколько конструкторов, но нужен по сути только самый первый, остальные для разыгравшейся фантазии. Инициализация при создании матрицы обязательна, поскольку может выдавать неправильный ответ в связи с забытым в памяти мусором. Как перемножать матрицы можно узнать здесь. Нам понадобятся три матрицы, исходная, временная и матрица для ответа. Само двоичное представление удобно хранить в строке, поскольку идя по ней и находя [latex]1[/latex] мы можем домножить на временную матрицу матрицу ответ.

#include <iostream>
#include <string>
#include <vector>
#include <deque>
using namespace std;

class matrix{ //создаем класс матрицы, в основном для красивого перемножения
    private:
        int n,m;
        int long long **arr;
    public:
        matrix(){
            n = 1; m = 1;
        }
        matrix(int x){
            n = x; m = x;
            arr = new int long long *[n];
            for(int i = 0; i < n; i++){
                arr[i] = new int long long [m];
            }
            for(int j = 0; j < this->n; j++){
                for(int k = 0; k < this->m; k++){
                    arr[j][k] = 0;
                }
            }
        }
        matrix(int x, int y){
            n = x; m = y;
            arr = new int long long *[n];
            for(int i = 0; i < n; i++){
                arr[i] = new int long long [m];
            }
            for(int j = 0; j < this->n; j++){ // необходимо инициализировать нулями,покольку в памяти может быть забытый мусор
                for(int k = 0; k < this->m; k++){
                    arr[j][k] = 0;
                }
            }
        } // выше были описанны конструкторы
        ~matrix(){
            for(int i = 0; i < n; i++){
                delete arr[i];
            }
            delete arr;
        }// деструктор
        void read(){
            for(int j = 0; j < this->n; j++){
                for(int k = 0; k < this->m; k++){
                    cin >> arr[j][k];
                }
            }
        }//функция ввода
        void write(){
            for(int j = 0; j < this->n; j++){
                for(int k = 0; k < this->m; k++){
                    cout << arr[j][k] << " ";
                }
                cout << endl;
            }
        }// функция вывода
        void create(int x, int y){
            n = x; m = y;
            arr = new int long long *[n];
            for(int i = 0; i < n; i++){
                arr[i] = new int long long [m];
            }
        }//функция измененияколичества выделяемой под нас памяти
        matrix& operator=(const matrix& x){
            for(int j = 0; j < this->n; j++){
                for(int k = 0; k < this->m; k++){
                    arr[j][k] = x.arr[j][k];
                }
            }
            return *this;
        }// переопределение оператора присваивания для матриц
        const matrix operator*(const matrix& x){
            matrix ans(this->n, this->m);
            for(int i = 0; i < this->n; i++){
                for(int j = 0; j < this->m; j++){
                    for(int k = 0; k < this->m; k++){
                        ans.arr[i][j]+= this-> arr[i][k] * x.arr[k][j];
                    }
                }
            }
            return ans;
        }//переопределение умножения для матриц
        matrix& operator*=(const matrix& x){
            matrix ans(this->n, this->m);
            for(int i = 0; i < this->n; i++){
                for(int j = 0; j < this->m; j++){
                    for(int k = 0; k < this->m; k++){
                        ans.arr[i][j]+= this-> arr[i][k] * x.arr[k][j];
                    }
                }
            }
            *this=ans;
            return *this;
        }//переопределение присвоить равно
        
        matrix& pow(int n){
            string s;
            for(int i = 0; i < sizeof(int)*8 -1; i++){// цикл где мы побитово сдвигаем вправо и умножаем на 1, если в этом бите была 1,то мы добавим в строку 1,если был 0,то 0 конъюнкия 1 будет 0
                s+= to_string((n >> i)&1);; 
            }
            int i = s.size()-1; // заводим переменную, в которой будет храниться наивисший разряд двойки
            for(; s[i]!= '1'; i--){} //находим этот разряд,двигаясь с конца в поисках первой 
            matrix ans(this->n,this->m);
            for(int j = 0; j < this->n; j++){
                for(int k = 0; k < this->m; k++){
                    if(j == k) ans.arr[j][k] = 1; else ans.arr[j][k] = 0; 
                }
            }
            matrix temp(this->n,this->m);
            temp = *this;
            for(int j = 0; j <= i; j++){
                if(s[j] == '1'){
                    ans*=temp;
                }
                temp*=temp;
            }
            *this=ans;
            return *this;
        }
};

int main() {
    int n,size = 2; string s; //n число,в которую нам надо возвести в степень,размеры матрицы и строка,в которой будем для удобства хранить двоичное представление числа
    cin >> n;
    matrix mas(size); // создаем матрицу
    mas.read();
    mas.pow(n);
    mas.write();
    return 0;
}

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

133

#include <iostream>

#include <string>

#include <vector>

#include <deque>

using namespace std;

class matrix{ //создаем класс матрицы, в основном для красивого перемножения

private:

int n,m;

int long long **arr;

public:

matrix(){

n = 1; m = 1;

}

matrix(int x){

n = x; m = x;

arr = new int long long *[n];

for(int i = 0; i < n; i++){

arr[i] = new int long long [m];

}

for(int j = 0; j < this->n; j++){

for(int k = 0; k < this->m; k++){

arr[j][k] = 0;

}

matrix(int x, int y){

n = x; m = y;

arr = new int long long *[n];

for(int i = 0; i < n; i++){

arr[i] = new int long long [m];

}

for(int j = 0; j < this->n; j++){ // необходимо инициализировать нулями,покольку в памяти может быть забытый мусор

for(int k = 0; k < this->m; k++){

arr[j][k] = 0;

}

} // выше были описанны конструкторы

~matrix(){

for(int i = 0; i < n; i++){

delete arr[i];

}

delete arr;

}// деструктор

void read(){

for(int j = 0; j < this->n; j++){

for(int k = 0; k < this->m; k++){

cin >> arr[j][k];

}

}//функция ввода

void write(){

for(int j = 0; j < this->n; j++){

for(int k = 0; k < this->m; k++){

cout << arr[j][k] << " ";

}

cout << endl;

}

}// функция вывода

void create(int x, int y){

n = x; m = y;

arr = new int long long *[n];

for(int i = 0; i < n; i++){

arr[i] = new int long long [m];

}

}//функция измененияколичества выделяемой под нас памяти

matrix& operator=(const matrix& x){

for(int j = 0; j < this->n; j++){

for(int k = 0; k < this->m; k++){

arr[j][k] = x.arr[j][k];

}

return *this;

}// переопределение оператора присваивания для матриц

const matrix operator*(const matrix& x){

matrix ans(this->n, this->m);

for(int i = 0; i < this->n; i++){

for(int j = 0; j < this->m; j++){

for(int k = 0; k < this->m; k++){

ans.arr[i][j]+= this-> arr[i][k] * x.arr[k][j];

}

return ans;

}//переопределение умножения для матриц

matrix& operator*=(const matrix& x){

matrix ans(this->n, this->m);

for(int i = 0; i < this->n; i++){

for(int j = 0; j < this->m; j++){

for(int k = 0; k < this->m; k++){

ans.arr[i][j]+= this-> arr[i][k] * x.arr[k][j];

}

*this=ans;

return *this;

}//переопределение присвоить равно

matrix& pow(int n){

string s;

for(int i = 0; i < sizeof(int)*8 -1; i++){// цикл где мы побитово сдвигаем вправо и умножаем на 1, если в этом бите была 1,то мы добавим в строку 1,если был 0,то 0 конъюнкия 1 будет 0

s+= to_string((n >> i)&1);;

}

int i = s.size()-1; // заводим переменную, в которой будет храниться наивисший разряд двойки

for(; s[i]!= '1'; i--){} //находим этот разряд,двигаясь с конца в поисках первой

matrix ans(this->n,this->m);

for(int j = 0; j < this->n; j++){

for(int k = 0; k < this->m; k++){

if(j == k) ans.arr[j][k] = 1; else ans.arr[j][k] = 0;

}

matrix temp(this->n,this->m);

temp = *this;

for(int j = 0; j <= i; j++){

if(s[j] == '1'){

ans*=temp;

}

temp*=temp;

}

*this=ans;

return *this;

}

};

int main() {

int n,size = 2; string s; //n число,в которую нам надо возвести в степень,размеры матрицы и строка,в которой будем для удобства хранить двоичное представление числа

cin >> n;

matrix mas(size); // создаем матрицу

mas.read();

mas.pow(n);

mas.write();

return 0;

}

link.

C++ для приматов

Начальный курс программирования для студентов направления "Прикладная математика" Одесского национального университета имени И.И.Мечникова

Tag Archives: Возведение матрицы в степень

e-olymp 8651. Браслети (Bangles)

Вхідні дані

Вихідні дані

Тести

Код

Рішення

Посилання

Related Images:

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

Задача

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

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

Тесты

Решение

Замечание

Ссылки

Related Images:

A708

Related Images:

А706 Алгоритм быстрого возведения в степень

Related Images: