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

graph/chromatic.hpp
linalg/blackbox/vandermonde.hpp
mod/q_analogue.hpp
poly/composition_f_log_1_minus_x.hpp
poly/from_log_differentiation.hpp
poly/multipoint.hpp
poly/multivar_convolution_cyclic.hpp
poly/partial_frac_decomposition_1.hpp
poly/sparse_exp_of_div.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/1080_2.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/3_yukicoder/502_2.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;
}