# library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub kazunetakahashi/library

# old/fast_fourier_transform.cpp

Back to top page

## Code

#include <iostream>
#include <complex>
#include <vector>
using namespace std;

const int N = (1 << 18); // 最大次数
const double PI = acos(-1);
typedef complex<double> comp;

vector<comp> dft(vector<comp> f, int n, bool doesinv)
{
if (n == 1)
return f;
vector<comp> f0, f1;
for (auto i = 0; i < n / 2; i++)
{
f0.push_back(f[2 * i]);
f1.push_back(f[2 * i + 1]);
}
f0 = dft(f0, n / 2, doesinv);
f1 = dft(f1, n / 2, doesinv);
comp zeta;
if (!doesinv)
{
zeta = comp(cos(2 * PI / n), sin(2 * PI / n));
}
else
{
zeta = comp(cos(2 * PI / n), -1 * sin(2 * PI / n));
}
comp pow_zeta = comp(1, 0);
for (auto i = 0; i < n; i++)
{
f[i] = f0[i % (n / 2)] + pow_zeta * f1[i % (n / 2)];
pow_zeta = pow_zeta * zeta;
}
return f;
}

vector<comp> multiply(vector<comp> g, vector<comp> h)
{
vector<comp> gg = dft(g, N, false);
vector<comp> hh = dft(h, N, false);
vector<comp> ff = vector<comp>(N);
for (auto i = 0; i < N; i++)
{
ff[i] = gg[i] * hh[i];
}
vector<comp> ans = dft(ff, N, true);
for (auto i = 0; i < N; i++)
{
ans[i] = ans[i] / comp(N, 0);
}
return ans;
}

int main()
{
}



#line 1 "old/fast_fourier_transform.cpp"
#include <iostream>
#include <complex>
#include <vector>
using namespace std;

const int N = (1 << 18); // 最大次数
const double PI = acos(-1);
typedef complex<double> comp;

vector<comp> dft(vector<comp> f, int n, bool doesinv)
{
if (n == 1)
return f;
vector<comp> f0, f1;
for (auto i = 0; i < n / 2; i++)
{
f0.push_back(f[2 * i]);
f1.push_back(f[2 * i + 1]);
}
f0 = dft(f0, n / 2, doesinv);
f1 = dft(f1, n / 2, doesinv);
comp zeta;
if (!doesinv)
{
zeta = comp(cos(2 * PI / n), sin(2 * PI / n));
}
else
{
zeta = comp(cos(2 * PI / n), -1 * sin(2 * PI / n));
}
comp pow_zeta = comp(1, 0);
for (auto i = 0; i < n; i++)
{
f[i] = f0[i % (n / 2)] + pow_zeta * f1[i % (n / 2)];
pow_zeta = pow_zeta * zeta;
}
return f;
}

vector<comp> multiply(vector<comp> g, vector<comp> h)
{
vector<comp> gg = dft(g, N, false);
vector<comp> hh = dft(h, N, false);
vector<comp> ff = vector<comp>(N);
for (auto i = 0; i < N; i++)
{
ff[i] = gg[i] * hh[i];
}
vector<comp> ans = dft(ff, N, true);
for (auto i = 0; i < N; i++)
{
ans[i] = ans[i] / comp(N, 0);
}
return ans;
}

int main()
{
}



Back to top page