fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. //Симметричная квадратная матрица порядка n задана линейным набором из
  5. //n(n+1)/2 элементов. Все методы класса оперируют только с таким представлением.
  6.  
  7. template <typename T>
  8. class symmetric_matrix{
  9. private:
  10. T* data;
  11. int data_size;
  12. public:
  13. //Конструкторы.
  14. symmetric_matrix(){}
  15. symmetric_matrix(int n){
  16. data = new T[(n*(n+1))/2];
  17. data_size = n;
  18. }
  19. symmetric_matrix(int n, int value){
  20. data = new T[(n*(n+1))/2];
  21. for(int i = 0; i < (n*(n+1))/2; i++)
  22. data[i] = value;
  23. data_size = n;
  24. }
  25. //Методы.
  26. int size(){ return data_size; }
  27. T get(int pos){ return data[pos]; }
  28. void set(int pos, T value){ data[pos] = value; }
  29. //Подпространство симметричных квадратные матриц заданного порядка
  30. //не замкнутно относительно операции матричного умножения.
  31. //Тем не менее, при возведение матрицы в степень замкнутость не
  32. //нарушается, в связи с чем операция умножения реализована для него.
  33. symmetric_matrix<T> operator *(symmetric_matrix<T> B){
  34. int n = data_size;
  35. symmetric_matrix<T> C(n);
  36. int curr = 0;
  37. for(int row = 0; row < n; row++){ //row
  38. for(int col = row; col < n; col++){ //col
  39. int rpos = row, cpos = col; //(row, col)
  40. int rstep = n-1, cstep = n-1; //row, col step
  41. for(int i = 0; i < n; i++){
  42. C.set(curr, C[curr] + data[rpos]*B[cpos]);
  43. rpos += (rstep >= n-row)*(rstep - 1) + 1;
  44. cpos += (cstep >= n-col)*(cstep - 1) + 1;
  45. rstep--, cstep--;
  46. }
  47. curr++;
  48. }
  49. }
  50. return C;
  51. }
  52.  
  53. //Операторы.
  54. T operator [](int pos){return data[pos];}
  55. symmetric_matrix<T> operator +(symmetric_matrix<T> B){
  56. int n = B.size();
  57. symmetric_matrix<T> C(n);
  58. for(int i = 0; i < (n*(n+1))/2; i++)
  59. C.set(i, data[i] + B[i]);
  60. return C;
  61. };
  62. symmetric_matrix<T> operator -(symmetric_matrix<T> B){
  63. int n = B.size();
  64. symmetric_matrix<T> C(n);
  65. for(int i = 0; i < (n*(n+1))/2; i++)
  66. C.set(i, data[i] - B[i]);
  67. return C;
  68. };
  69. };
  70.  
  71. //Бинарный алгоритм возведения матрицы в степень.
  72. template <typename T>
  73. symmetric_matrix<T> power(symmetric_matrix<T> A, int n){
  74. symmetric_matrix<T> result(A.size());
  75. //Изначально result - нейтральный элемент относительно умножения
  76. //т.е. единичная матрица.
  77. for(int i = 0, diag = 0; i < A.size(); i++){
  78. result.set(diag, 1);
  79. diag += A.size()-i;
  80. }
  81. while(n){
  82. if(n & 1)
  83. result = result * A;
  84. A = A * A;
  85. n >>= 1;
  86. }
  87. return result;
  88. }
  89.  
  90.  
  91. int main(){
  92. int n; cin >> n;
  93. symmetric_matrix<int> A(n), B(n), C(n);
  94. //Считывание данных
  95. for(int i = 0; i < (n*(n+1))/2; i++){
  96. int value; cin >> value;
  97. A.set(i, value);
  98. }
  99. for(int i = 0; i < (n*(n+1))/2; i++){
  100. int value; cin >> value;
  101. B.set(i, value);
  102. }
  103.  
  104. C = power(A, 2) - power(B, 2);
  105. for(int i = 0; i < (n*(n+1))/2; i++){
  106. cout << C.get(i) << " ";
  107. }
  108. return 0;
  109. }
  110.  
Success #stdin #stdout 0s 3232KB
stdin
4
1 7 3 -2 3 1 9 2 8 11
4 5 11 -3 4 -7 22 1 4 0
stdout
-108 116 -8 -79 -434 -10 75 -109 290 -239