Advertisement
Merevoli

Untitled

Jul 16th, 2022
133
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.50 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. #define matrix_type vector<vector<unsigned long long>>
  5.  
  6. const long long MOD = 1e7 + 7;
  7. const int MAX_POW = 2022;
  8.  
  9. bitset <2022 * 4> bin_n;
  10. int len_bin_n = 0;
  11.  
  12. int char_to_int(char c){
  13. return (int)c - 48;
  14. }
  15.  
  16. char int_to_char(int d){
  17. return (char)(d + 48);
  18. }
  19.  
  20. void count_bit_1_str(string s){
  21. int ind = 0;
  22. bin_n.reset();
  23.  
  24. while (s != ""){
  25. int last_digit = char_to_int(s[s.length() - 1]);
  26. if (last_digit & 1){
  27. s[s.length() - 1] = int_to_char(last_digit - 1);
  28. bin_n[ind] = 1;
  29. }
  30.  
  31. int current_digit;
  32. for (int i=s.length() - 1; i>=0; i--){
  33. current_digit = char_to_int(s[i]);
  34.  
  35. s[i] = int_to_char(current_digit / 2);
  36. if (current_digit & 1){
  37. s[i + 1] = int_to_char(char_to_int(s[i + 1]) + 5);
  38. }
  39. }
  40.  
  41. if (s[0] == '0'){
  42. s.erase(0, 1);
  43. }
  44. ind++;
  45. }
  46. len_bin_n = ind - 1;
  47. }
  48.  
  49. matrix_type mul_matrix(matrix_type matrix_1, matrix_type matrix_2){
  50. matrix_type result_matrix(matrix_1.size(), vector<unsigned long long>(matrix_2[0].size(), 0));
  51.  
  52. for (int a=0; a<matrix_1.size(); a++){
  53. for (int b=0; b<matrix_2[0].size(); b++){
  54. unsigned long long s = 0;
  55. for (int c=0; c<matrix_1[0].size(); c++){
  56. s += matrix_1[a][c] * matrix_2[c][b];
  57. }
  58. result_matrix[a][b] = s;
  59. }
  60. }
  61.  
  62. return result_matrix;
  63. }
  64.  
  65. void mod_matrix(matrix_type &matrix){
  66. for (int i=0; i<matrix.size(); i++){
  67. for (int j=0; j<matrix[i].size(); j++){
  68. matrix[i][j] %= MOD;
  69. }
  70. }
  71. }
  72.  
  73. void print_matrix(matrix_type matrix){
  74. for (int i=0; i<matrix.size(); i++){
  75. for (int j=0; j<matrix[i].size(); j++){
  76. cerr << matrix[i][j] << ' ';
  77. }
  78. cerr << '\n';
  79. }
  80. cerr << '\n';
  81. }
  82.  
  83. matrix_type pow_matrix(int current_ind, matrix_type &base_matrix, matrix_type &unit_matrix){
  84. if (current_ind == len_bin_n){
  85. if (bin_n[len_bin_n]){
  86. return base_matrix;
  87. }
  88. else{
  89. return unit_matrix;
  90. }
  91. }
  92. else{
  93. matrix_type result_matrix;
  94. matrix_type pow_2 = pow_matrix(current_ind + 1, base_matrix, unit_matrix);
  95.  
  96. if (bin_n[current_ind]){
  97. result_matrix = mul_matrix(mul_matrix(pow_2, pow_2), base_matrix);
  98. mod_matrix(result_matrix);
  99. return result_matrix;
  100. }
  101. else{
  102. result_matrix = mul_matrix(pow_2, pow_2);
  103. mod_matrix(result_matrix);
  104. return result_matrix;
  105. }
  106. }
  107. }
  108.  
  109. int main(){
  110. // freopen("input.txt", "r", stdin);
  111. // freopen("output.txt", "w", stdout);
  112.  
  113. string n;
  114. unsigned long long ta, tb, tc;
  115. unsigned long long pa, pb, pc;
  116. cin >> n;
  117. cin >> ta >> tb >> tc;
  118. cin >> pa >> pb >> pc;
  119.  
  120. matrix_type base_matrix = {
  121. {pa - 2, 1, 1},
  122. {1, pb - 2, 1},
  123. {1, 1, pc - 2}
  124. };
  125.  
  126. matrix_type unit_matrix = {
  127. {1, 0, 0},
  128. {0, 1, 0},
  129. {0, 0, 1}
  130. };
  131.  
  132. matrix_type t_matrix = {
  133. {ta},
  134. {tb},
  135. {tc}
  136. };
  137.  
  138. count_bit_1_str(n);
  139.  
  140. matrix_type result_matrix = mul_matrix(pow_matrix(0, base_matrix, unit_matrix), t_matrix);
  141. mod_matrix(result_matrix);
  142.  
  143. cout << result_matrix[0][0] << ' ' << result_matrix[1][0] << ' ' << result_matrix[2][0];
  144. }
  145.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement