複数の要素の逆元を一括で計算
(modint/multi-inverse.hpp)

• View this file on GitHub
• Last update: 2025-10-31 21:40:36+09:00
• Include: #include "modint/multi-inverse.hpp"

Required by

• 多項式補間 (fps/polynomial-interpolation.hpp)

Verified with

• verify/fps/LC_polynomial_interpolation.test.cpp
• verify/fps/LC_polynomial_interpolation_on_geometric_sequence.test.cpp
• verify/fps/UNIT_prefix_sum_of_polynomial.test.cpp
• verify/modint/UNIT_multi_inverse.test.cpp

Code

#pragma once

template <class mint>
vector<mint> MultiInverse(const vector<mint>& a) {
  if (a.empty()) return {};
  vector<mint> b(a.begin(), a.end());
  for (int i = 0; i + 1 < b.size(); i++) b[i + 1] *= b[i];
  mint c = b.back().inv();
  for (int i = a.size() - 1; i > 0; i--) {
    b[i] = c * b[i - 1];
    c *= a[i];
  }
  b[0] = c;
  return b;
}
/**
 * @brief 複数の要素の逆元を一括で計算
 */

#line 2 "modint/multi-inverse.hpp"

template <class mint>
vector<mint> MultiInverse(const vector<mint>& a) {
  if (a.empty()) return {};
  vector<mint> b(a.begin(), a.end());
  for (int i = 0; i + 1 < b.size(); i++) b[i + 1] *= b[i];
  mint c = b.back().inv();
  for (int i = a.size() - 1; i > 0; i--) {
    b[i] = c * b[i - 1];
    c *= a[i];
  }
  b[0] = c;
  return b;
}
/**
 * @brief 複数の要素の逆元を一括で計算
 */

Back to top page