batch_inv.hpp

• View this file on GitHub
• Last update: 2025-01-19 15:28:01+08:00
• Include: #include "batch_inv.hpp"

Required by

• Chirp Z Transform (czt.hpp)
• Polynomial Interpolation (Lagrange Interpolation) (poly_interpolation.hpp)
• poly_interpolation_with_error.hpp
• Shift Sample Points (shift_sample_points.hpp)
• Subproduct Tree (subproduct_tree.hpp)

Verified with

• test/enumerative_combinatorics/factorial.0.test.cpp
• test/formal_power_series/conversion_from_monomial_basis_to_newton_basis.0.test.cpp
• test/formal_power_series/multipoint_evaluation.0.test.cpp
• test/formal_power_series/multipoint_evaluation_on_geometric_sequence.0.test.cpp
• test/formal_power_series/polynomial_interpolation.0.test.cpp
• test/formal_power_series/polynomial_interpolation_on_geometric_sequence.0.test.cpp
• test/formal_power_series/shift_of_sampling_points_of_polynomial.1.test.cpp

Code

#pragma once

#include <cassert>
#include <vector>

template<typename Tp> inline std::vector<Tp> batch_inv(const std::vector<Tp> &a) {
    if (a.empty()) return {};
    const int n = a.size();
    std::vector<Tp> b(n);
    Tp v = 1;
    for (int i = 0; i < n; ++i) b[i] = v, v *= a[i];
    assert(v != 0);
    v = v.inv();
    for (int i = n - 1; i >= 0; --i) b[i] *= v, v *= a[i];
    return b;
}

#line 2 "batch_inv.hpp"

#include <cassert>
#include <vector>

template<typename Tp> inline std::vector<Tp> batch_inv(const std::vector<Tp> &a) {
    if (a.empty()) return {};
    const int n = a.size();
    std::vector<Tp> b(n);
    Tp v = 1;
    for (int i = 0; i < n; ++i) b[i] = v, v *= a[i];
    assert(v != 0);
    v = v.inv();
    for (int i = n - 1; i >= 0; --i) b[i] *= v, v *= a[i];
    return b;
}

Back to top page