#include <algorithm>
#include<iostream>
#include <cstdio>
#include <ctime>
#include <vector>
#include <complex>
using namespace std;
#define cd complex<double>
#define vcd vector<cd>
#define si(n) scanf("%d",&n)
#define f(i,a,b) for(int i=a;i<b;i++)
#define pb push_back
vcd fft(const vcd &as) {
int n = as.size();
int k = 0;
while ((1 << k) < n) k++;
vector<int> rev(n);
rev[0] = 0;
int high1 = -1;
for (int i = 1; i < n; i++) {
if ((i & (i - 1)) == 0)
high1++;
rev[i] = rev[i ^ (1 << high1)];
rev[i] |= (1 << (k - high1 - 1));
}
vcd roots(n);
for (int i = 0; i < n; i++) {
double alpha = 2 * M_PI * i / n;
roots[i] = cd(cos(alpha), sin(alpha));
}
vcd cur(n);
for (int i = 0; i < n; i++)
cur[i] = as[rev[i]];
for (int len = 1; len < n; len <<= 1) {
vcd ncur(n);
int rstep = roots.size() / (len * 2);
for (int pdest = 0; pdest < n;) {
int p1 = pdest;
for (int i = 0; i < len; i++) {
cd val = roots[i * rstep] * cur[p1 + len];
ncur[pdest] = cur[p1] + val;
ncur[pdest + len] = cur[p1] - val;
pdest++, p1++;
}
pdest += len;
}
cur.swap(ncur);
}
return cur;
}
vcd fft_rev(const vcd &as) {
vcd res = fft(as);
for (int i = 0; i < (int)res.size(); i++) res[i] /= as.size();
reverse(res.begin() + 1, res.end());
return res;
}
//the coeffeciets of input polynomial are stored in a vector-> vcd
int power(int num,int n)
{
if(n==1) return num;
int p= power(num,n/2);
p= (p*p);
if(n%2!=0)
{
p=(p*num);
}
return p;
}
int main()
{
//cout<<ceil(log2(5))<<"\n";
cout<<"Input the degree of polynomials to be multiplied\n";
int n,a;
si(n);
vcd P,Q;
cout<<"Enter first polynomial coeffecients\n";
f(i,0,n+1)
{
si(a);
P.pb(cd(a,0));
}
cout<<"Enter second polynomial coeffecients\n";
f(i,0,n+1)
{
si(a);
P.pb(cd(a,0));
}
int t;
t=n*2;
int p=ceil(log2(t));
t=power(2,p);
f(i,n+1,t+1)
{
P.pb(0);
Q.pb(0);
}
vcd P1,Q1;
P1= fft(P);
Q1= fft(Q);
vcd E;
f(i,0,t+1)
{
E.pb(P1[i]*Q1[i]);
}
vcd Res;
Res= fft_rev(E);
cout<<"the final product coeffeciets are: \n";
f(i,0,t+1)
{
cout<<Res[i]<<" ";
}
cout<<"\n";
return 0;
}
I2luY2x1ZGUgPGFsZ29yaXRobT4KI2luY2x1ZGU8aW9zdHJlYW0+CiNpbmNsdWRlIDxjc3RkaW8+CiNpbmNsdWRlIDxjdGltZT4KI2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGUgPGNvbXBsZXg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiNkZWZpbmUgY2QgY29tcGxleDxkb3VibGU+CiNkZWZpbmUgdmNkIHZlY3RvcjxjZD4KI2RlZmluZSBzaShuKSBzY2FuZigiJWQiLCZuKQojZGVmaW5lIGYoaSxhLGIpIGZvcihpbnQgaT1hO2k8YjtpKyspCiNkZWZpbmUgcGIgcHVzaF9iYWNrCgp2Y2QgZmZ0KGNvbnN0IHZjZCAmYXMpIHsKICBpbnQgbiA9IGFzLnNpemUoKTsKICBpbnQgayA9IDA7CiAgd2hpbGUgKCgxIDw8IGspIDwgbikgaysrOwogIHZlY3RvcjxpbnQ+IHJldihuKTsKICByZXZbMF0gPSAwOwogIGludCBoaWdoMSA9IC0xOwogIGZvciAoaW50IGkgPSAxOyBpIDwgbjsgaSsrKSB7CiAgICBpZiAoKGkgJiAoaSAtIDEpKSA9PSAwKQogICAgICBoaWdoMSsrOwogICAgcmV2W2ldID0gcmV2W2kgXiAoMSA8PCBoaWdoMSldOwogICAgcmV2W2ldIHw9ICgxIDw8IChrIC0gaGlnaDEgLSAxKSk7CiAgfQoKICB2Y2Qgcm9vdHMobik7CiAgZm9yIChpbnQgaSA9IDA7IGkgPCBuOyBpKyspIHsKICAgIGRvdWJsZSBhbHBoYSA9IDIgKiBNX1BJICogaSAvIG47CiAgICByb290c1tpXSA9IGNkKGNvcyhhbHBoYSksIHNpbihhbHBoYSkpOwogIH0KCiAgdmNkIGN1cihuKTsKICBmb3IgKGludCBpID0gMDsgaSA8IG47IGkrKykKICAgIGN1cltpXSA9IGFzW3JldltpXV07CgogIGZvciAoaW50IGxlbiA9IDE7IGxlbiA8IG47IGxlbiA8PD0gMSkgewogICAgdmNkIG5jdXIobik7CiAgICBpbnQgcnN0ZXAgPSByb290cy5zaXplKCkgLyAobGVuICogMik7CiAgICBmb3IgKGludCBwZGVzdCA9IDA7IHBkZXN0IDwgbjspIHsKICAgICAgaW50IHAxID0gcGRlc3Q7CiAgICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbGVuOyBpKyspIHsKICAgICAgICBjZCB2YWwgPSByb290c1tpICogcnN0ZXBdICogY3VyW3AxICsgbGVuXTsKICAgICAgICBuY3VyW3BkZXN0XSA9IGN1cltwMV0gKyB2YWw7CiAgICAgICAgbmN1cltwZGVzdCArIGxlbl0gPSBjdXJbcDFdIC0gdmFsOwogICAgICAgIHBkZXN0KyssIHAxKys7CiAgICAgIH0KICAgICAgcGRlc3QgKz0gbGVuOwogICAgfQogICAgY3VyLnN3YXAobmN1cik7CiAgfQogIHJldHVybiBjdXI7Cn0KCnZjZCBmZnRfcmV2KGNvbnN0IHZjZCAmYXMpIHsKICB2Y2QgcmVzID0gZmZ0KGFzKTsKICBmb3IgKGludCBpID0gMDsgaSA8IChpbnQpcmVzLnNpemUoKTsgaSsrKSByZXNbaV0gLz0gYXMuc2l6ZSgpOwogIHJldmVyc2UocmVzLmJlZ2luKCkgKyAxLCByZXMuZW5kKCkpOwogIHJldHVybiByZXM7Cn0KLy90aGUgY29lZmZlY2lldHMgb2YgaW5wdXQgcG9seW5vbWlhbCBhcmUgc3RvcmVkIGluIGEgdmVjdG9yLT4gdmNkCmludCBwb3dlcihpbnQgbnVtLGludCBuKQp7CiAgICBpZihuPT0xKSByZXR1cm4gbnVtOwogICAgaW50IHA9IHBvd2VyKG51bSxuLzIpOwogICAgcD0gKHAqcCk7CiAgICBpZihuJTIhPTApCiAgICB7CiAgICAgICAgcD0ocCpudW0pOwogICAgfQogICAgcmV0dXJuIHA7Cn0KCmludCBtYWluKCkKewogICAgLy9jb3V0PDxjZWlsKGxvZzIoNSkpPDwiXG4iOwogICAgY291dDw8IklucHV0IHRoZSBkZWdyZWUgb2YgcG9seW5vbWlhbHMgdG8gYmUgbXVsdGlwbGllZFxuIjsKICAgIGludCBuLGE7CiAgICBzaShuKTsKICAgIHZjZCBQLFE7CiAgICBjb3V0PDwiRW50ZXIgZmlyc3QgcG9seW5vbWlhbCBjb2VmZmVjaWVudHNcbiI7CiAgICBmKGksMCxuKzEpCiAgICB7CiAgICAgICAgc2koYSk7CiAgICAgICAgUC5wYihjZChhLDApKTsKICAgIH0KICAgIGNvdXQ8PCJFbnRlciBzZWNvbmQgcG9seW5vbWlhbCBjb2VmZmVjaWVudHNcbiI7CiAgICBmKGksMCxuKzEpCiAgICB7CiAgICAgICAgc2koYSk7CiAgICAgICAgUC5wYihjZChhLDApKTsKICAgIH0KICAgIGludCB0OwogICAgdD1uKjI7CiAgICBpbnQgcD1jZWlsKGxvZzIodCkpOwogICAgdD1wb3dlcigyLHApOwogICAgZihpLG4rMSx0KzEpCiAgICB7CiAgICAgICAgUC5wYigwKTsKICAgICAgICBRLnBiKDApOwogICAgfQogICAgdmNkIFAxLFExOwogICAgUDE9IGZmdChQKTsKICAgIFExPSBmZnQoUSk7CiAgICB2Y2QgRTsKICAgIGYoaSwwLHQrMSkKICAgIHsKICAgICAgICBFLnBiKFAxW2ldKlExW2ldKTsKICAgIH0KICAgIHZjZCBSZXM7CiAgICBSZXM9IGZmdF9yZXYoRSk7CiAgICBjb3V0PDwidGhlIGZpbmFsIHByb2R1Y3QgY29lZmZlY2lldHMgYXJlOiBcbiI7CiAgICBmKGksMCx0KzEpCiAgICB7CiAgICAgICAgY291dDw8UmVzW2ldPDwiICI7CiAgICB9CiAgICBjb3V0PDwiXG4iOwogICAgcmV0dXJuIDA7Cn0K