alg/monoid/arithmetic_expression.hpp

• View this file on GitHub
• Last update: 2024-10-16 22:34:39+09:00
• Include: #include "alg/monoid/arithmetic_expression.hpp"
• Link: https://ac.nowcoder.com/acm/contest/81599/K

Code

// https://ac.nowcoder.com/acm/contest/81599/K

/*
type=0: empty
type=1: a
type=2: a*b*c
type=3: a*b+c+d*e
左端(a,c,e)の桁数の10べきももつ
*/
template <typename mint>
struct Arithmetic_Expression {
  int type;
  mint a, b, c, d, e, ten;
  Arithmetic_Expression(char ch = ' ') {
    if (ch == ' ') { type = 0; }
    elif (ch == '+') { type = 3, a = 0, b = 1, c = 0, d = 1, e = 0, ten = 1; }
    elif (ch == '*') { type = 2, a = 0, b = 1, c = 0, ten = 1; }
    elif ('0' <= ch && ch <= '9') { type = 1, a = (ch - '0'), ten = 10; }
    else {
      assert(0);
    }
  }
  mint eval() {
    if (type == 0) return 0;
    if (type == 1) return a;
    if (type == 2) return a * b * c;
    if (type == 3) return a * b + c + d * e;
    assert(0);
    return 0;
  }
};

template <typename mint>
struct Monoid_Arithmetic_Expression {
  using value_type = Arithmetic_Expression<mint>;
  using X = value_type;
  static X op(const X& L, const X& R) {
    if (L.type == 0) return R;
    if (R.type == 0) return L;
    assert(1 <= L.type && L.type <= 3);
    assert(1 <= R.type && R.type <= 3);
    X ANS;
    if (L.type == 1 && R.type == 1) {
      ANS.type = 1, ANS.a = L.a * R.ten + R.a;
      ANS.ten = L.ten * R.ten;
    }
    if (L.type == 1 && R.type == 2) {
      ANS.type = 2, ANS.a = L.a * R.ten + R.a, ANS.b = R.b, ANS.c = R.c;
      ANS.ten = L.ten * R.ten;
    }
    if (L.type == 1 && R.type == 3) {
      ANS.type = 3, ANS.a = L.a * R.ten + R.a, ANS.b = R.b, ANS.c = R.c, ANS.d = R.d, ANS.e = R.e;
      ANS.ten = L.ten * R.ten;
    }
    if (L.type == 2 && R.type == 1) {
      ANS.type = 2, ANS.a = L.a, ANS.b = L.b, ANS.c = L.c * R.ten + R.a;
      ANS.ten = L.ten;
    }
    if (L.type == 2 && R.type == 2) {
      ANS.type = 2;
      ANS.a = L.a, ANS.b = L.b * (L.c * R.ten + R.a) * R.b, ANS.c = R.c;
      ANS.ten = L.ten;
    }
    if (L.type == 2 && R.type == 3) {
      ANS.type = 3;
      ANS.a = L.a, ANS.b = L.b * (L.c * R.ten + R.a) * R.b, ANS.c = R.c, ANS.d = R.d, ANS.e = R.e;
      ANS.ten = L.ten;
    }
    if (L.type == 3 && R.type == 1) {
      ANS.type = 3;
      ANS.a = L.a, ANS.b = L.b, ANS.c = L.c, ANS.d = L.d, ANS.e = (L.e * R.ten + R.a);
      ANS.ten = L.ten;
    }
    if (L.type == 3 && R.type == 2) {
      ANS.type = 3;
      ANS.a = L.a, ANS.b = L.b, ANS.c = L.c, ANS.d = L.d * (L.e * R.ten + R.a) * R.b, ANS.e = R.c;
      ANS.ten = L.ten;
    }
    if (L.type == 3 && R.type == 3) {
      ANS.type = 3;
      ANS.a = L.a, ANS.b = L.b, ANS.c = L.c + L.d * (L.e * R.ten + R.a) * R.b + R.c, ANS.d = R.d, ANS.e = R.e;
      ANS.ten = L.ten;
    }
    return ANS;
  }
  static constexpr X unit() { return X(); }
  static constexpr bool commute = 0;
};

#line 1 "alg/monoid/arithmetic_expression.hpp"
// https://ac.nowcoder.com/acm/contest/81599/K

/*
type=0: empty
type=1: a
type=2: a*b*c
type=3: a*b+c+d*e
左端(a,c,e)の桁数の10べきももつ
*/
template <typename mint>
struct Arithmetic_Expression {
  int type;
  mint a, b, c, d, e, ten;
  Arithmetic_Expression(char ch = ' ') {
    if (ch == ' ') { type = 0; }
    elif (ch == '+') { type = 3, a = 0, b = 1, c = 0, d = 1, e = 0, ten = 1; }
    elif (ch == '*') { type = 2, a = 0, b = 1, c = 0, ten = 1; }
    elif ('0' <= ch && ch <= '9') { type = 1, a = (ch - '0'), ten = 10; }
    else {
      assert(0);
    }
  }
  mint eval() {
    if (type == 0) return 0;
    if (type == 1) return a;
    if (type == 2) return a * b * c;
    if (type == 3) return a * b + c + d * e;
    assert(0);
    return 0;
  }
};

template <typename mint>
struct Monoid_Arithmetic_Expression {
  using value_type = Arithmetic_Expression<mint>;
  using X = value_type;
  static X op(const X& L, const X& R) {
    if (L.type == 0) return R;
    if (R.type == 0) return L;
    assert(1 <= L.type && L.type <= 3);
    assert(1 <= R.type && R.type <= 3);
    X ANS;
    if (L.type == 1 && R.type == 1) {
      ANS.type = 1, ANS.a = L.a * R.ten + R.a;
      ANS.ten = L.ten * R.ten;
    }
    if (L.type == 1 && R.type == 2) {
      ANS.type = 2, ANS.a = L.a * R.ten + R.a, ANS.b = R.b, ANS.c = R.c;
      ANS.ten = L.ten * R.ten;
    }
    if (L.type == 1 && R.type == 3) {
      ANS.type = 3, ANS.a = L.a * R.ten + R.a, ANS.b = R.b, ANS.c = R.c, ANS.d = R.d, ANS.e = R.e;
      ANS.ten = L.ten * R.ten;
    }
    if (L.type == 2 && R.type == 1) {
      ANS.type = 2, ANS.a = L.a, ANS.b = L.b, ANS.c = L.c * R.ten + R.a;
      ANS.ten = L.ten;
    }
    if (L.type == 2 && R.type == 2) {
      ANS.type = 2;
      ANS.a = L.a, ANS.b = L.b * (L.c * R.ten + R.a) * R.b, ANS.c = R.c;
      ANS.ten = L.ten;
    }
    if (L.type == 2 && R.type == 3) {
      ANS.type = 3;
      ANS.a = L.a, ANS.b = L.b * (L.c * R.ten + R.a) * R.b, ANS.c = R.c, ANS.d = R.d, ANS.e = R.e;
      ANS.ten = L.ten;
    }
    if (L.type == 3 && R.type == 1) {
      ANS.type = 3;
      ANS.a = L.a, ANS.b = L.b, ANS.c = L.c, ANS.d = L.d, ANS.e = (L.e * R.ten + R.a);
      ANS.ten = L.ten;
    }
    if (L.type == 3 && R.type == 2) {
      ANS.type = 3;
      ANS.a = L.a, ANS.b = L.b, ANS.c = L.c, ANS.d = L.d * (L.e * R.ten + R.a) * R.b, ANS.e = R.c;
      ANS.ten = L.ten;
    }
    if (L.type == 3 && R.type == 3) {
      ANS.type = 3;
      ANS.a = L.a, ANS.b = L.b, ANS.c = L.c + L.d * (L.e * R.ten + R.a) * R.b + R.c, ANS.d = R.d, ANS.e = R.e;
      ANS.ten = L.ten;
    }
    return ANS;
  }
  static constexpr X unit() { return X(); }
  static constexpr bool commute = 0;
};

Back to top page