fork(3) download
copy 
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. #include <deque>
  5. using namespace std;
  6.  
  7. class matrix{ //создаем класс матрицы, в основном для красивого перемножения
  8. 	private:
  9. 		int n,m;
  10. 		int long long **arr;
  11. 	public:
  12. 		matrix(){
  13. 			n = 1; m = 1;
  14. 		}
  15. 		matrix(int x){
  16. 			n = x; m = x;
  17. 			arr = new int long long *[n];
  18. 			for(int i = 0; i < n; i++){
  19. 				arr[i] = new int long long [m];
  20. 			}
  21. 			for(int j = 0; j < this->n; j++){
  22. 				for(int k = 0; k < this->m; k++){
  23. 					arr[j][k] = 0;
  24. 				}
  25. 			}
  26. 		}
  27. 		matrix(int x, int y){
  28. 			n = x; m = y;
  29. 			arr = new int long long *[n];
  30. 			for(int i = 0; i < n; i++){
  31. 				arr[i] = new int long long [m];
  32. 			}
  33. 			for(int j = 0; j < this->n; j++){ // необходимо инициализировать нулями,покольку в памяти может быть забытый мусор
  34. 				for(int k = 0; k < this->m; k++){
  35. 					arr[j][k] = 0;
  36. 				}
  37. 			}
  38. 		} // выше были описанны конструкторы
  39. 		~matrix(){
  40. 			for(int i = 0; i < n; i++){
  41. 				delete arr[i];
  42. 			}
  43. 			delete arr;
  44. 		}// деструктор
  45. 		void read(){
  46. 			for(int j = 0; j < this->n; j++){
  47. 				for(int k = 0; k < this->m; k++){
  48. 					cin >> arr[j][k];
  49. 				}
  50. 			}
  51. 		}//функция ввода
  52. 		void write(){
  53. 			for(int j = 0; j < this->n; j++){
  54. 				for(int k = 0; k < this->m; k++){
  55. 					cout << arr[j][k] << " ";
  56. 				}
  57. 				cout << endl;
  58. 			}
  59. 		}// функция вывода
  60. 		void create(int x, int y){
  61. 			n = x; m = y;
  62. 			arr = new int long long *[n];
  63. 			for(int i = 0; i < n; i++){
  64. 				arr[i] = new int long long [m];
  65. 			}
  66. 		}//функция измененияколичества выделяемой под нас памяти
  67. 		matrix& operator=(const matrix& x){
  68. 			for(int j = 0; j < this->n; j++){
  69. 				for(int k = 0; k < this->m; k++){
  70. 					arr[j][k] = x.arr[j][k];
  71. 				}
  72. 			}
  73. 			return *this;
  74. 		}// переопределение оператора присваивания для матриц
  75. 		const matrix operator*(const matrix& x){
  76. 			matrix ans(this->n, this->m);
  77. 			for(int i = 0; i < this->n; i++){
  78. 				for(int j = 0; j < this->m; j++){
  79. 					for(int k = 0; k < this->m; k++){
  80. 						ans.arr[i][j]+= this-> arr[i][k] * x.arr[k][j];
  81. 					}
  82. 				}
  83. 			}
  84. 			return ans;
  85. 		}//переопределение умножения для матриц
  86. 		matrix& operator*=(const matrix& x){
  87. 			matrix ans(this->n, this->m);
  88. 			for(int i = 0; i < this->n; i++){
  89. 				for(int j = 0; j < this->m; j++){
  90. 					for(int k = 0; k < this->m; k++){
  91. 						ans.arr[i][j]+= this-> arr[i][k] * x.arr[k][j];
  92. 					}
  93. 				}
  94. 			}
  95. 			*this=ans;
  96. 			return *this;
  97. 		}//переопределение присвоить равно
  98.  
  99. 		matrix& pow(int n){
  100. 			string s;
  101. 			for(int i = 0; i < sizeof(int)*8 -1; i++){// цикл где мы побитово сдвигаем вправо и умножаем на 1, если в этом бите была 1,то мы добавим в строку 1,если был 0,то 0 конъюнкия 1 будет 0
  102. 				s+= to_string((n >> i)&1);; 
  103. 			}
  104. 			int i = s.size()-1; // заводим переменную, в которой будет храниться наивисший разряд двойки
  105. 			for(; s[i]!= '1'; i--){} //находим этот разряд,двигаясь с конца в поисках первой 
  106. 			matrix ans(this->n,this->m);
  107. 			for(int j = 0; j < this->n; j++){
  108. 				for(int k = 0; k < this->m; k++){
  109. 					if(j == k) ans.arr[j][k] = 1; else ans.arr[j][k] = 0; 
  110. 				}
  111. 			}
  112. 			matrix temp(this->n,this->m);
  113. 			temp = *this;
  114. 			for(int j = 0; j <= i; j++){
  115. 				if(s[j] == '1'){
  116. 					ans*=temp;
  117. 				}
  118. 				temp*=temp;
  119. 			}
  120. 			*this=ans;
  121. 			return *this;
  122. 		}
  123. };
  124.  
  125. int main() {
  126. 	int n,size = 2; string s; //n число,в которую нам надо возвести в степень,размеры матрицы и строка,в которой будем для удобства хранить двоичное представление числа
  127. 	cin >> n;
  128. 	matrix mas(size); // создаем матрицу
  129. 	mas.read();
  130. 	mas.pow(n);
  131. 	mas.write();
  132. 	return 0;
  133. }
Success #stdin #stdout 0s 3280KB
comments (?)
stdin
copy 
2
0 1
2 3
stdout
copy 
2 3 
6 11
https://ideone.com/98TJTu
Перемножение матриц
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!