ds/power_query.hpp

• View this file on GitHub
• Last update: 2022-12-05 18:15:30+09:00
• Include: #include "ds/power_query.hpp"

Depends on

• alg/monoid/mul.hpp

Required by

• graph/count/count_bipartite.hpp

Verified with

• test/mytest/count_bipartite.test.cpp
• test/mytest/powerquery.test.cpp

Code

#include "alg/monoid/mul.hpp"

// 定数をべき乗するクエリ。 B 乗分ずつ前計算。
template <typename Mono, int B = 1024>
struct Power_Query {
  using X = typename Mono::value_type;
  vvc<X> dat;

  Power_Query(X a) { dat.eb(make_pow(a)); }

  X operator()(ll n) {
    X res = Mono::unit();
    int k = 0;
    while (n) {
      int r = n % B;
      n /= B;
      if (len(dat) == k) { dat.eb(make_pow(dat[k - 1].back())); }
      res = Mono::op(res, dat[k][r]);
      ++k;
    }
    return res;
  }

  X operator[](ll n) { return (*this)(n); }

private:
  vc<X> make_pow(X a) {
    vc<X> res = {Mono::unit()};
    FOR(B) { res.eb(Mono::op(res.back(), a)); }
    return res;
  }
};

#line 2 "alg/monoid/mul.hpp"

template <class T>
struct Monoid_Mul {
  using value_type = T;
  using X = T;
  static constexpr X op(const X &x, const X &y) noexcept { return x * y; }
  static constexpr X inverse(const X &x) noexcept { return X(1) / x; }
  static constexpr X unit() { return X(1); }
  static constexpr bool commute = true;
};
#line 2 "ds/power_query.hpp"

// 定数をべき乗するクエリ。 B 乗分ずつ前計算。
template <typename Mono, int B = 1024>
struct Power_Query {
  using X = typename Mono::value_type;
  vvc<X> dat;

  Power_Query(X a) { dat.eb(make_pow(a)); }

  X operator()(ll n) {
    X res = Mono::unit();
    int k = 0;
    while (n) {
      int r = n % B;
      n /= B;
      if (len(dat) == k) { dat.eb(make_pow(dat[k - 1].back())); }
      res = Mono::op(res, dat[k][r]);
      ++k;
    }
    return res;
  }

  X operator[](ll n) { return (*this)(n); }

private:
  vc<X> make_pow(X a) {
    vc<X> res = {Mono::unit()};
    FOR(B) { res.eb(Mono::op(res.back(), a)); }
    return res;
  }
};

Back to top page