fps/FPS_cyclic_convolution.hpp

• View this file on GitHub
• Last update: 2024-06-19 00:51:37+09:00
• Include: #include "fps/FPS_cyclic_convolution.hpp"

Required by

• fps/FPS_exp.hpp
• fps/FPS_inverse.hpp
• fps/FPS_pow.hpp
• fps/Multipoint_Evaluation_Geo.hpp

Verified with

• test/fps/comp_inverse.test.cpp
• test/fps/exp.test.cpp
• test/fps/multpoint_evalution_geo.test.cpp
• test/fps/pow.test.cpp

Code

#pragma once
#include <vector>
#include <atcoder/convolution>

namespace po167{
// |f| = |g| = 2 ^ n
template<class T>
std::vector<T> FPS_cyclic_convolution(std::vector<T> f, std::vector<T> g){
    atcoder::internal::butterfly(f);
    atcoder::internal::butterfly(g);
    for (int i = 0; i < (int)f.size(); i++) f[i] *= g[i];
    atcoder::internal::butterfly_inv(f);
    T iz = (T)(1) / (T)(f.size());
    for (int i = 0; i < (int)f.size(); i++) f[i] *= iz;
    return f;
}
}

#line 2 "fps/FPS_cyclic_convolution.hpp"
#include <vector>
#include <atcoder/convolution>

namespace po167{
// |f| = |g| = 2 ^ n
template<class T>
std::vector<T> FPS_cyclic_convolution(std::vector<T> f, std::vector<T> g){
    atcoder::internal::butterfly(f);
    atcoder::internal::butterfly(g);
    for (int i = 0; i < (int)f.size(); i++) f[i] *= g[i];
    atcoder::internal::butterfly_inv(f);
    T iz = (T)(1) / (T)(f.size());
    for (int i = 0; i < (int)f.size(); i++) f[i] *= iz;
    return f;
}
}

Back to top page