Advertisement
Saleh127

SPOJ Polynomial Multiplication / Fast Fourier transform

Aug 14th, 2022
1,154
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.39 KB | None | 0 0
  1. /***
  2.  created: 2022-08-14-23.16.33
  3. ***/
  4.  
  5. #include <bits/stdc++.h>
  6. #include <ext/pb_ds/assoc_container.hpp>
  7. #include <ext/pb_ds/tree_policy.hpp>
  8. using namespace std;
  9. using namespace __gnu_pbds;
  10. template<typename U> using ordered_set=tree<U, null_type,less<U>,rb_tree_tag,tree_order_statistics_node_update>;
  11. #define ll long long
  12. #define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
  13. #define get_lost_idiot return 0
  14. #define nl '\n'
  15. #define PI acos(-1.0)
  16. typedef complex<double> base;
  17.  
  18. void fft(vector<base> & a, bool invert) {
  19.     int n = (int)a.size();
  20.  
  21.     for (int i = 1, j = 0; i<n; ++i) {
  22.         int bit = n >> 1;
  23.         for (; j >= bit; bit >>= 1)j -= bit;
  24.         j += bit;
  25.         if (i < j)swap(a[i], a[j]);
  26.     }
  27.  
  28.     for (int len = 2; len <= n; len <<= 1) {
  29.         double ang = 2 * PI / len * (invert ? -1 : 1);
  30.         base wlen(cos(ang), sin(ang));
  31.         for (int i = 0; i<n; i += len) {
  32.             base w(1);
  33.             for (int j = 0; j<len / 2; ++j) {
  34.                 base u = a[i + j], v = a[i + j + len / 2] * w;
  35.                 a[i + j] = u + v;
  36.                 a[i + j + len / 2] = u - v;
  37.                 w *= wlen;
  38.             }
  39.         }
  40.     }
  41.     if (invert)for (int i = 0; i<n; ++i)a[i] /= n;
  42. }
  43. vector<ll> Mul(vector<ll>& a, vector<ll>& b)
  44. {
  45.     vector<base> fa(a.begin(), a.end()), fb(b.begin(), b.end());
  46.     int n = 1;
  47.     while (n < max(a.size(), b.size()))  n <<= 1;
  48.     n <<= 1;
  49.     fa.resize(n), fb.resize(n);
  50.  
  51.     fft(fa, false), fft(fb, false);
  52.     for (int i = 0; i<n; ++i)fa[i] *= fb[i];
  53.     fft(fa, true);
  54.  
  55.     vector<ll> res;
  56.     res.resize(n);
  57.     for (int i = 0; i<n; ++i)res[i] = round(fa[i].real());
  58.  
  59. //  int carry=0;
  60. //
  61. //  for(int i=0;i<n;i++)
  62. //    {
  63. //        res[i]+=carry;
  64. //        carry=res[i]/10;
  65. //        res[i]%=10;
  66. //    }
  67.  
  68.     while(res.size()>1 && res.back()==0)
  69.     {
  70.         res.pop_back();
  71.     }
  72.  
  73.     //reverse(res.begin(),res.end());
  74.  
  75.     return res;
  76. }
  77.  
  78. int main()
  79. {
  80.     ios_base::sync_with_stdio(0);
  81.     cin.tie(0);
  82.     cout.tie(0);
  83.  
  84.  
  85.     test
  86.     {
  87.         ll i,n,m,j,k,l;
  88.  
  89.         vector<ll>x,y,ans;
  90.  
  91.         cin>>n;
  92.  
  93.         for(i=0;i<=n;i++)
  94.         {
  95.             cin>>m;
  96.             x.push_back(m);
  97.         }
  98.  
  99.         for(i=0;i<=n;i++)
  100.         {
  101.             cin>>m;
  102.             y.push_back(m);
  103.         }
  104.  
  105.         reverse(x.begin(),x.end());
  106.         reverse(y.begin(),y.end());
  107.  
  108.         ans=Mul(x,y);
  109.  
  110.         for(i=ans.size()-1;i>=0;i--)
  111.         {
  112.             cout<<ans[i]<<" ";
  113.         }
  114.  
  115.         cout<<nl;
  116.  
  117.     }
  118.  
  119.     get_lost_idiot;
  120. }
  121.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement