Product of Polynomials
(FPS/prodofpolys.hpp)

• View this file on GitHub
• Last update: 2023-01-16 20:41:46+09:00
• Include: #include "FPS/prodofpolys.hpp"

Required by

• Find roots (FPS/findroots.hpp)
• Enumerate $\sum_k a_k^i$ (FPS/sumofpowers.hpp)

Verified with

• Verify/LC_product_of_polynomial_sequence.test.cpp

Code

#pragma once

template<typename T>Poly<T> ProdOfPolys(vector<Poly<T>>& fs){
    if(fs.empty())return Poly<T>({T(1)});
    sort(ALL(fs),[&](Poly<T>& a,Poly<T>& b){return a.size()<b.size();});
    deque<Poly<T>> deq;
    for(auto& f:fs)deq.push_back(f);
    while(deq.size()>1){
        deq.push_back(deq[0]*deq[1]);
        deq.pop_front();
        deq.pop_front();
    }
    return deq[0];
}

/**
 * @brief Product of Polynomials
*/

#line 2 "FPS/prodofpolys.hpp"

template<typename T>Poly<T> ProdOfPolys(vector<Poly<T>>& fs){
    if(fs.empty())return Poly<T>({T(1)});
    sort(ALL(fs),[&](Poly<T>& a,Poly<T>& b){return a.size()<b.size();});
    deque<Poly<T>> deq;
    for(auto& f:fs)deq.push_back(f);
    while(deq.size()>1){
        deq.push_back(deq[0]*deq[1]);
        deq.pop_front();
        deq.pop_front();
    }
    return deq[0];
}

/**
 * @brief Product of Polynomials
*/

Back to top page