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"
• Link: View error logs on GitHub Actions

Required by

• graph/chromatic.hpp
• 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
• seq/p_recursive.hpp

Verified with

• test/1_mytest/all_inverse.test.cpp
• test/1_mytest/chirp_z.test.cpp
• test/1_mytest/composition_log_1_minus_x.test.cpp
• test/1_mytest/partial_frac.test.cpp
• test/1_mytest/qbinom.test.cpp
• test/1_mytest/vandermonde.test.cpp
• test/2_library_checker/convolution/multivariate_convolution_cyclic.test.cpp
• test/2_library_checker/graph/chromatic_number.test.cpp
• test/2_library_checker/graph/chromatic_polynomial.test.cpp
• test/2_library_checker/polynomial/multipoint_evaluation.test.cpp
• test/2_library_checker/polynomial/multipoint_evaluation_on_geom.test.cpp
• test/2_library_checker/polynomial/multipoint_evaluation_on_geom_2.test.cpp
• test/2_library_checker/polynomial/polynomial_interpolation.test.cpp
• test/2_library_checker/polynomial/polynomial_interpolation_on_geom.test.cpp
• test/3_yukicoder/1575.test.cpp
• test/3_yukicoder/2166.test.cpp
• test/3_yukicoder/2243.test.cpp
• test/3_yukicoder/2877.test.cpp
• test/5_atcoder/abc241h.test.cpp
• test/5_atcoder/abc260h.test.cpp
• test/5_atcoder/abc267g.test.cpp
• test/5_atcoder/abc272_h.test.cpp
• test/5_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