fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. using cd=complex<double>;
  4. const double PI=acos(-1);
  5. void fft(vector<cd> &a,bool invert)
  6. {
  7.     int n=a.size();
  8.     if(n==1) return;
  9.     vector<cd> a0(n>>1),a1(n>>1);
  10.     for(int i=0;(i<<1)<n;i++){
  11.         a0[i]=a[i<<1];
  12.         a1[i]=a[(i<<1)+1];
  13.     }
  14.     fft(a0,invert);
  15.     fft(a1,invert);
  16.     double ang=2*PI/n*(invert?-1:1);
  17.     cd w(1),wn(cos(ang),sin(ang));
  18.     for(int i=0;(i<<1)<n;i++){
  19.         a[i]=a0[i]+w*a1[i];
  20.         a[i+(n>>1)]=a0[i]-w*a1[i];
  21.         if(invert){
  22.             a[i]/=2;
  23.             a[i+(n>>1)]/=2;
  24.         }
  25.         w*=wn;
  26.     }
  27. }
  28. vector<double> mul(vector<double> &a,vector<double> &b)
  29. {
  30.     vector<cd> fa(a.begin(),a.end()),fb(b.begin(),b.end());
  31.     int n=1;
  32.     while(n<a.size()+b.size()){
  33.         n<<=1;
  34.     }
  35.     fa.resize(n);
  36.     fb.resize(n);
  37.     fft(fa,0);
  38.     fft(fb,0);
  39.     for(int i=0;i<n;i++){
  40.         fa[i]*=fb[i];
  41.     }
  42.     fft(fa,1);
  43.     vector<double> ans(n);
  44.     for(int i=0;i<n;i++){
  45.         ans[i]=fa[i].real();
  46.     }
  47.     return ans;
  48. }
  49. int main()
  50. {
  51.     ios_base::sync_with_stdio(false);
  52.     cin.tie(0);
  53.     cout.tie(0);
  54.     int t;
  55.     cin>>t;
  56.     while(t--){
  57.         int n,m;
  58.         cin>>n>>m;
  59.         n++;
  60.         m++;
  61.         vector<double> a(n),b(m);
  62.         for(int i=0;i<n;i++){
  63.             cin>>a[i];
  64.         }
  65.         for(int i=0;i<m;i++){
  66.             cin>>b[i];
  67.         }
  68.         vector<double> ans=mul(a,b);
  69.         for(int i=0;i<n+m-1;i++){
  70.             cout<<setprecision(6)<<fixed<<ans[i]<<" ";
  71.         }
  72.         cout<<"\n";
  73.     }
  74. }
  75.  
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin
copy 
1
3 3
0.1 0.2 0.3 0.4
0.5 0.6 0.7 0.8
stdout
copy 
0.050000 0.160000 0.340000 0.600000 0.610000 0.520000 0.320000
https://ideone.com/1E8XHS
language:
C++14 (gcc 8.3)
created:
5 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!