mod/all_inverse.hpp

• View this file on GitHub
• Last update: 2022-11-23 08:11:54+09:00
• Include: #include "mod/all_inverse.hpp"

Required by

• linalg/blackbox/vandermonde.hpp
• mod/q_analogue.hpp
• poly/composition_f_log_1_minus_x.hpp
• poly/multipoint.hpp
• poly/multivar_convolution_cyclic.hpp
• poly/partial_frac_decomposition_1.hpp

Verified with

• test/library_checker/math/multivariate_convolution_cyclic.test.cpp
• test/library_checker/polynomial/multipoint_evaluation.test.cpp
• test/library_checker/polynomial/multipoint_evaluation_on_geom.test.cpp
• test/library_checker/polynomial/multipoint_evaluation_on_geom_2.test.cpp
• test/library_checker/polynomial/polynomial_interpolation.test.cpp
• test/library_checker/polynomial/polynomial_interpolation_on_geom.test.cpp
• test/mytest/all_inverse.test.cpp
• test/mytest/chirp_z.test.cpp
• test/mytest/composition_log_1_minus_x.test.cpp
• test/mytest/partial_frac.test.cpp
• test/mytest/qbinom.test.cpp
• test/mytest/vandermonde.test.cpp
• test/yukicoder/1575.test.cpp
• test/yukicoder/2166.test.cpp
• test/yukicoder/2243.test.cpp
• test_atcoder/abc241h.test.cpp
• test_atcoder/abc260h.test.cpp
• test_atcoder/abc267g.test.cpp
• test_atcoder/abc272_h.test.cpp
• test_atcoder/agc058d2.test.cpp

Code

#pragma once
template <typename mint>
vc<mint> all_inverse(vc<mint>& X) {
  for (auto&& x: X) assert(x != mint(0));
  int N = len(X);
  vc<mint> res(N + 1);
  res[0] = mint(1);
  FOR(i, N) res[i + 1] = res[i] * X[i];
  mint t = res.back().inverse();
  res.pop_back();
  FOR_R(i, N) {
    res[i] *= t;
    t *= X[i];
  }
  return res;
}

#line 2 "mod/all_inverse.hpp"
template <typename mint>
vc<mint> all_inverse(vc<mint>& X) {
  for (auto&& x: X) assert(x != mint(0));
  int N = len(X);
  vc<mint> res(N + 1);
  res[0] = mint(1);
  FOR(i, N) res[i + 1] = res[i] * X[i];
  mint t = res.back().inverse();
  res.pop_back();
  FOR_R(i, N) {
    res[i] *= t;
    t *= X[i];
  }
  return res;
}

Back to top page