Skip to content

Instantly share code, notes, and snippets.

@koosaga
Last active Aug 1, 2021
Embed
What would you like to do?
typedef long long lint;
namespace fft{
typedef complex<double> base;
void fft(vector<base> &v, bool inv){
vector<base> w(v.size());
for(int i=2; i<=v.size(); i<<=1){
int bsz = v.size() / i;
base ang(cos(2 * M_PI / i), sin(2 * M_PI / i));
if(inv) ang = base(1, 0) / ang;
for(int j=0; j<bsz; j++){
for(int k=0; k<i; k++){
w[k] = v[bsz * k + j];
}
base pw(1, 0);
for(int k=0; k<i/2; k++){
base a = w[2*k], b = w[2*k+1] * pw;
v[bsz * k + j] = a + b;
v[bsz * k + j + v.size()/2] = a - b;
pw *= ang;
}
}
}
if(inv){
for(int i=0; i<v.size(); i++){
v[i] /= v.size();
}
}
}
vector<lint> multiply(vector<lint> &v, vector<lint> &w){
vector<base> fv(v.begin(), v.end()), fw(w.begin(), w.end());
int n = 1;
while(n < max(v.size(), w.size())) n <<= 1;
n <<= 1;
fv.resize(n);
fw.resize(n);
fft(fv, 0);
fft(fw, 0);
for(int i=0; i<n; i++) fv[i] *= fw[i];
fft(fv, 1);
vector<lint> ret(n);
for(int i=0; i<n; i++) ret[i] = round(fv[i].real());
return ret;
}
vector<lint> power(vector<lint> &v){
vector<base> fv(v.begin(), v.end());
int n = 1;
while(n < v.size()) n <<= 1;
n <<= 1;
fv.resize(n);
fft(fv, 0);
for(int i=0; i<n; i++) fv[i] *= fv[i];
fft(fv, 1);
vector<lint> ret(n);
for(int i=0; i<n; i++) ret[i] = round(fv[i].real());
return ret;
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment