alg/acted_monoid/powersums_assign.hpp

View this file on GitHub
Last update: 2023-10-14 20:28:40+09:00
Include: #include "alg/acted_monoid/powersums_assign.hpp"

Depends on

Verified with

test/yukicoder/1548.test.cpp

Code

#pragma once

#include "alg/monoid/assign.hpp"
#include "alg/monoid/add_array.hpp"

// 0, 1, ..., K 乗和

template <typename T, int K>
struct ActedMonoid_Power_Sums_Assign {
  using Monoid_X = Monoid_Add_Array<T, K + 1>;
  using Monoid_A = Monoid_Assign<T, -1>;
  using X = typename Monoid_X::value_type;
  using A = typename Monoid_A::value_type;
  static constexpr X act(const X &x, const A &a, const ll &size) {
    if (a == Monoid_A::unit()) return x;
    X y;
    T pow = 1;
    FOR(i, K + 1) { y[i] = x[0] * pow, pow *= a; }
    return y;
  }
};

#line 2 "alg/acted_monoid/powersums_assign.hpp"

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

template <typename X, int none_val>
struct Monoid_Assign {
  using value_type = X;
  static X op(X x, X y) { return (y == X(none_val) ? x : y); }
  static constexpr X unit() { return X(none_val); }
  static constexpr bool commute = false;
};
#line 2 "alg/monoid/add_array.hpp"

template <typename E, int K>
struct Monoid_Add_Array {
  using value_type = array<E, K>;
  using X = value_type;
  static X op(X x, X y) {
    FOR(i, K) x[i] += y[i];
    return x;
  }
  static constexpr X unit() { return X{}; }
  static constexpr X inverse(X x) {
    for (auto& v: x) v = -v;
    return x;
  }
  static constexpr X power(X x, ll n) {
    for (auto& v: x) v *= E(n);
    return x;
  }
  static constexpr bool commute = 1;
};
#line 5 "alg/acted_monoid/powersums_assign.hpp"

// 0, 1, ..., K 乗和

template <typename T, int K>
struct ActedMonoid_Power_Sums_Assign {
  using Monoid_X = Monoid_Add_Array<T, K + 1>;
  using Monoid_A = Monoid_Assign<T, -1>;
  using X = typename Monoid_X::value_type;
  using A = typename Monoid_A::value_type;
  static constexpr X act(const X &x, const A &a, const ll &size) {
    if (a == Monoid_A::unit()) return x;
    X y;
    T pow = 1;
    FOR(i, K + 1) { y[i] = x[0] * pow, pow *= a; }
    return y;
  }
};