fork(3) download
  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
stdin
2
0 1
2 3
stdout
2 3 
6 11