library/algebra/group/Affine.hpp

View this file on GitHub
Last update: 2025-11-24 18:49:07+09:00
Include: #include "library/algebra/group/Affine.hpp"

Depends on

Required by

library/algebra/lazy/AffineSum.hpp

Verified with

Code

#pragma once
#include "library/linearalgebra/Linear.hpp"
template <typename T> struct GroupAffine {
    using L = Line<T>;
    using value_type = L;
    static constexpr L op(const L &f, const L &g) noexcept { return f(g); }
    static constexpr void Rchop(L &f, const L &g) {
        f.b += f.a * g.b;
        f.a *= g.a;
    }
    static constexpr void Lchop(const L &f, L &g) {
        (g.b *= f.a) += f.b;
        g.a *= f.a;
    }
    static constexpr L inverse(const L &f) { return f.inv(); }
    /*
    static constexpr L power(const L& f,long long n) noexcept {
      if(a==1)return {1,n*b};
      K an=power(a,n);
      return {an,b*((1-an)/(1-a))};
    }
    */
    static constexpr L unit() { return L(1, 0); }
    static constexpr bool commute = false;
};

#line 2 "library/linearalgebra/Linear.hpp"
template <typename T> struct Line {
    T a, b;
    Line() = default;
    Line(T a, T b) : a(a), b(b) {}
    Line(std::pair<T, T> l) : a(l.first), b(l.second) {}
    Line(T c) : a(0), b(c) {}

    T operator()(const T x) const { return a * x + b; }
    Line operator()(const Line &l) const { return Line(a * l.a, a * l.b + b); }

    bool operator==(const Line &l) const { return a == l.a and b == l.b; }
    bool operator!=(const Line &l) const { return !(*this == l); }
    bool operator<(const Line &l) const {
        return (a == l.a ? a < l.a : b < l.b);
    }

    Line &operator+=(const Line &l) {
        a += l.a;
        b += l.b;
        return *this;
    }
    Line operator+(const Line &l) const { return Line(*this) += l; }
    Line &operator-=(const Line &l) {
        a -= l.a;
        b -= l.b;
        return *this;
    }
    Line operator-(const Line &l) const { return Line(*this) -= l; }
    Line operator-() const { return Line(-a, -b); }

    Line &operator+=(const T &c) {
        b += c;
        return *this;
    }
    Line operator+(const T &c) const { return Line(*this) += c; }
    Line &operator-=(const T &c) {
        b -= c;
        return *this;
    }
    Line operator-(const T &c) const { return Line(*this) -= c; }
    Line &operator*=(const T &c) {
        a *= c;
        b *= c;
        return *this;
    }
    Line operator*(const T &c) const { return Line(*this) *= c; }
    Line &operator/=(const T &c) {
        a /= c;
        b /= c;
        return *this;
    }
    Line operator/(const T &c) const { return Line(*this) /= c; }

    Line inv() const {
        assert(a != 0);
        return Line(T(1) / a, -b / a);
    }

    friend std::istream &operator>>(std::istream &is, Line &l) {
        is >> l.a >> l.b;
        return is;
    }
    friend std::ostream &operator<<(std::ostream &os, const Line &l) {
        if (l.a == 0 and l.b == 0)
            os << 0;
        else if (l.a == 0)
            os << l.b;
        else if (l.b == 0)
            os << l.a << "x";
        else if (l.b > 0)
            os << l.a << "x+" << l.b;
        else
            os << l.a << "x-" << -l.b;
        return os;
    }
};
#line 3 "library/algebra/group/Affine.hpp"
template <typename T> struct GroupAffine {
    using L = Line<T>;
    using value_type = L;
    static constexpr L op(const L &f, const L &g) noexcept { return f(g); }
    static constexpr void Rchop(L &f, const L &g) {
        f.b += f.a * g.b;
        f.a *= g.a;
    }
    static constexpr void Lchop(const L &f, L &g) {
        (g.b *= f.a) += f.b;
        g.a *= f.a;
    }
    static constexpr L inverse(const L &f) { return f.inv(); }
    /*
    static constexpr L power(const L& f,long long n) noexcept {
      if(a==1)return {1,n*b};
      K an=power(a,n);
      return {an,b*((1-an)/(1-a))};
    }
    */
    static constexpr L unit() { return L(1, 0); }
    static constexpr bool commute = false;
};