all_product
(src/fps/all_product.hpp)

• View this file on GitHub
• Last update: 2024-11-09 01:34:39+09:00
• Include: #include "src/fps/all_product.hpp"

all_product

FPS<T> all_product(vector<FPS<T>> f)

$n$ 個の多項式 $f_0, f_1, …, f_{n - 1}$ に対して $\prod\limits_{i = 0}^{n - 1} f_i$ を返します．

計算量

$f_i$ の次数を $d_i$ とし， $N := \sum\limits_{i = 0}^{n - 1} d_i$ としたとき，

• $O(N \log^2 {N})$

Depends on

• template (src/template/template.hpp)

Verified with

• verify/library_checker/polynomial/product_of_polynomial_sequence.test.cpp

Code

#pragma once
#include "../template/template.hpp"
template <template <typename> typename FPS, typename T>
FPS<T> all_product(vector<FPS<T>> f) {
    if(f.empty()) return {1};
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    for(int i = 0; i < (int)f.size(); ++i) pq.emplace(f[i].size(), i);
    while((int)pq.size() > 1) {
        const auto [d1, i1] = pq.top();
        pq.pop();
        const auto [d2, i2] = pq.top();
        pq.pop();
        f[i1] *= f[i2];
        f[i2].clear();
        pq.emplace(d1 + d2, i1);
    }
    return f[pq.top().second];
}

#line 2 "src/template/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<long long, long long>;
#define rep(i, a, b) for(long long i = (a); i < (b); ++i)
#define rrep(i, a, b) for(long long i = (a); i >= (b); --i)
constexpr long long inf = 4e18;
struct SetupIO {
    SetupIO() {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout << fixed << setprecision(30);
    }
} setup_io;
#line 3 "src/fps/all_product.hpp"
template <template <typename> typename FPS, typename T>
FPS<T> all_product(vector<FPS<T>> f) {
    if(f.empty()) return {1};
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    for(int i = 0; i < (int)f.size(); ++i) pq.emplace(f[i].size(), i);
    while((int)pq.size() > 1) {
        const auto [d1, i1] = pq.top();
        pq.pop();
        const auto [d2, i2] = pq.top();
        pq.pop();
        f[i1] *= f[i2];
        f[i2].clear();
        pq.emplace(d1 + d2, i1);
    }
    return f[pq.top().second];
}

Back to top page