other/all_but_one_products.hpp

• View this file on GitHub
• Last update: 2022-10-01 13:28:06+09:00
• Include: #include "other/all_but_one_products.hpp"

Verified with

• test/mytest/all_but_one_products.test.cpp

Code

template <typename Monoid, typename X = typename Monoid::value_type>
vector<X> all_but_one_products(const vc<X>& A) {
  int N = len(A);
  vc<X> res(N, Monoid::unit());
  FOR(i, N - 1) res[i + 1] = Monoid::op(res[i], A[i]);
  X x = Monoid::unit();
  FOR_R(i, N) {
    res[i] = Monoid::op(res[i], x);
    x = Monoid::op(A[i], x);
  }
  return res;
}

#line 1 "other/all_but_one_products.hpp"
template <typename Monoid, typename X = typename Monoid::value_type>
vector<X> all_but_one_products(const vc<X>& A) {
  int N = len(A);
  vc<X> res(N, Monoid::unit());
  FOR(i, N - 1) res[i + 1] = Monoid::op(res[i], A[i]);
  X x = Monoid::unit();
  FOR_R(i, N) {
    res[i] = Monoid::op(res[i], x);
    x = Monoid::op(A[i], x);
  }
  return res;
}

Back to top page