Advertisement
GerONSo

karatsuba not work

Sep 25th, 2019
99
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.73 KB | None | 0 0
  1. /*
  2.  
  3. ∧_∧
  4. ( ・ω・。)つ━☆・*。
  5. ⊂  ノ    ・゜
  6. しーJ   Accepted
  7.  
  8. */
  9.  
  10. // #pragma GCC optimize("O3")
  11. // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  12.  
  13. #include<bits/stdc++.h>
  14. #include <ext/pb_ds/assoc_container.hpp>
  15. #include <ext/pb_ds/tree_policy.hpp>
  16.  
  17. #define ll long long
  18. #define all(x) begin(x), end(x)
  19. #define x first
  20. #define y second
  21. #define int unsigned int
  22.  
  23. using namespace std;
  24. using namespace __gnu_pbds;
  25.  
  26. typedef pair<int, int> pii;
  27. typedef long double ld;
  28. template<typename T>
  29. using kawaii_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  30.  
  31. const ld PI = atan2(0, -1);
  32.  
  33. void seriy() {
  34. // ios::sync_with_stdio(0);
  35. cin.tie(0);
  36. cout.tie(0);
  37. cout << fixed << setprecision(14);
  38. #ifdef _offline
  39. freopen("input.txt", "r", stdin);
  40. freopen("output.txt", "w", stdout);
  41. #endif
  42. }
  43.  
  44. const int MAXN = 100 + 10;
  45. const int MAXM = 600;
  46. const int INF = INT_MAX;
  47. const int MOD = 1e9 + 7;
  48. const int MAXLOG = 61;
  49.  
  50. void simple_multiply(vector<int> &a, vector<int> &b, vector<int> &res) {
  51. res.resize(a.size() + b.size());
  52. for(int i = 0; i < b.size(); i++) {
  53. for(int j = 0; j < a.size(); j++) {
  54. res[i + j] += b[i] * a[j];
  55. }
  56. }
  57. }
  58.  
  59. void sum(vector<int> &a, vector<int> &b, vector<int> &res) {
  60. res.resize(max(a.size(), b.size()));
  61. if(a.size() < b.size()) {
  62. swap(a, b);
  63. }
  64. res = a;
  65. for(int i = 0; i < b.size(); i++) {
  66. res[i] += b[i];
  67. }
  68. }
  69.  
  70. void out(vector<int> &a) {
  71. for(auto i : a) {
  72. cerr << i << " ";
  73. }
  74. cerr << '\n';
  75. }
  76.  
  77. void multiply(vector<int> &a, vector<int> &b, vector<int> &res) {
  78. if(max(a.size(), b.size()) < 100) {
  79. simple_multiply(a, b, res);
  80. return;
  81. }
  82. if(a.size() < b.size()) {
  83. swap(a, b);
  84. }
  85.  
  86. while(b.size() < a.size()) {
  87. b.push_back(0);
  88. }
  89. while((b.size() & (b.size() - 1))) {
  90. a.push_back(0);
  91. b.push_back(0);
  92. }
  93. int mid = a.size() / 2;
  94. vector<int> al, ar, bl, br;
  95. for(int i = 0; i < a.size(); i++) {
  96. if(i < mid) {
  97. al.push_back(a[i]);
  98. bl.push_back(b[i]);
  99. }
  100. else {
  101. ar.push_back(a[i]);
  102. br.push_back(b[i]);
  103. }
  104. }
  105. vector<int> r1, r2, r3, r4;
  106. multiply(al, bl, r1);
  107. multiply(al, br, r2);
  108. multiply(ar, bl, r3);
  109. multiply(ar, br, r4);
  110. reverse(all(r1));
  111. reverse(all(r2));
  112. reverse(all(r3));
  113. reverse(all(r4));
  114. // res.resize(a.size() + b.size() - 1);
  115. for(int i = 0; i < mid; i++) {
  116. r2.push_back(0);
  117. }
  118. for(int i = 0; i < mid; i++) {
  119. r3.push_back(0);
  120. }
  121. for(int i = 0; i < 2 * mid; i++) {
  122. r4.push_back(0);
  123. }
  124. reverse(all(r1));
  125. reverse(all(r2));
  126. reverse(all(r3));
  127. reverse(all(r4));
  128. // out(r1);
  129. // out(r2);
  130. // out(r3);
  131. // out(r4);
  132. sum(r1, r2, res);
  133. vector<int> res2;
  134. sum(res, r3, res2);
  135. res = {};
  136. sum(res2, r4, res);
  137. }
  138.  
  139. signed main() {
  140. seriy();
  141. vector<vector<int>> a;
  142. string s;
  143. while(getline(cin, s)) {
  144. a.push_back(vector<int>());
  145. stringstream ss(s);
  146. string w;
  147. while(ss >> w) {
  148. a.back().push_back(stoi(w));
  149. }
  150. }
  151. for(int i = 0; i < a.size() - 1; i++) {
  152. vector<int> res;
  153. multiply(a[i], a[i + 1], res);
  154. a[i + 1] = res;
  155. while(a[i + 1].back() == 0) {
  156. a[i + 1].pop_back();
  157. }
  158. }
  159.  
  160. bool was = 0;
  161. for(auto i : a.back()) {
  162. cout << i << " ";
  163. }
  164. //1 4 13 18 18
  165. return 0;
  166. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement