Advertisement
Guest User

Untitled

a guest
Sep 21st, 2019
118
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.60 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <string>
  4. #include <cmath>
  5. #include <math.h>
  6. #include <complex>
  7. #include <vector>
  8.  
  9. using namespace std;
  10. typedef long long ll;
  11. typedef complex<double> cd;
  12. typedef vector<complex<double>> vcd;
  13.  
  14. const double PI = acos(-1);
  15. const ll mod = 998244353;
  16.  
  17. int rev(int ind, int bit) {
  18. int res = 0;
  19. for (int i = 0; i < bit; i++) {
  20. if (ind & (1 << i)) {
  21. res |= (1 << (bit - i - 1));
  22. }
  23. }
  24. return res;
  25. }
  26.  
  27. void fft(vcd& a, int flag) {
  28. int n = (int)a.size();
  29. int bit = 0;
  30. while ((1 << bit) < n) bit++;
  31. for (int i = 0; i < n; i++) {
  32. if (i < rev(i, bit))
  33. swap(a[i], a[rev(i, bit)]);
  34. }
  35. for (int step = 2; step <= n; step *= 2) {
  36. cd wl(cos(2 * PI / step), flag * sin(2 * PI / step));
  37. for (int i = 0; i < n; i += step) {
  38. cd w(1, 0);
  39. for (int j = 0; j < step / 2; j++) {
  40. cd u = a[i + j], v = a[i + j + step / 2] * w;
  41. a[i + j] = u + v;
  42. a[i + j + step / 2] = u - v;
  43. w *= wl;
  44. }
  45. }
  46. }
  47. if (flag == -1) {
  48. for (cd& i : a) i /= n;
  49. }
  50. }
  51.  
  52. vector<ll> operator*(vector<ll> a, vector<ll> b) {
  53. vcd a1(a.begin(), a.end());
  54. vcd b1(b.begin(), b.end());
  55. int n = 1;
  56. while (n <= a.size() + b.size()) n <<= 1;
  57. a1.resize(n);
  58. b1.resize(n);
  59. fft(a1, 1);
  60. fft(b1, 1);
  61. for (int i = 0; i < n; i++) {
  62. a1[i] *= b1[i];
  63. }
  64. fft(a1, -1);
  65. a.clear(); a.resize(n);
  66. for (int i = 0; i < n; i++) {
  67. a[i] = (ll)(a1[i].real() + 0.5) % mod;
  68. }
  69. return a;
  70. }
  71.  
  72. const double eps = 1e-9;
  73.  
  74. int main() {
  75. freopen("multiply.in", "r", stdin);
  76. freopen("multiply.out", "w", stdout);
  77. string st1, st2;
  78. cin >> st1 >> st2;
  79. int mm = (st1[0] == '-') + (st2[0] == '-');
  80. if (st1[0] == '-') st1 = st1.substr(1);
  81. if (st2[0] == '-') st2 = st2.substr(1);
  82. if (st1[0] == '0' || st2[0] == '0') {
  83. cout << 0 << endl;
  84. return 0;
  85. }
  86. vector<ll> a1(st1.size()), a2(st2.size());
  87. for (int i = 0; i < st1.size(); i++) {
  88. a1[i] = st1[i] - '0';
  89. }
  90. for (int i = 0; i < st2.size(); i++) {
  91. a2[i] = st2[i] - '0';
  92. }
  93. a1 = a1 * a2;
  94. ll carry = 0;
  95. for (int i = a1.size() - 1; i > 0; i--) {
  96. a1[i] += carry;
  97. carry = a1[i] / 10;
  98. a1[i] %= 10;
  99. }
  100. a1[0] += carry;
  101. string ans;
  102. for (ll x : a1) ans += to_string(x);
  103. int len = (int)(st1.size() + st2.size()) - 1;
  104. string s3 = st1.substr(0, min((int)st1.size(), 8));
  105. string s4 = st2.substr(0, min((int)st2.size(), 8));
  106. double x1 = stod(s3), x2 = stod(s4);
  107. while (x1 + eps > 10) x1 /= 10;
  108. while (x2 + eps > 10) x2 /= 10;
  109. double x = x1 * x2;
  110. if (x - eps > 10) len++;
  111. while (ans.size() > len) ans.pop_back();
  112. if (mm % 2) cout << '-';
  113. cout << ans << endl;
  114. return 0;
  115. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement