cp-algo/math/affine.hpp

• View this file on GitHub
• Last update: 2024-05-14 16:05:25+02:00
• Include: #include "cp-algo/math/affine.hpp"

Required by

• cp-algo/linalg/frobenius.hpp
• cp-algo/math/poly.hpp
• cp-algo/math/poly/impl/euclid.hpp
• cp-algo/number_theory.hpp
• cp-algo/number_theory/discrete_sqrt.hpp
• cp-algo/structures/segtree/metas/affine.hpp
• cp-algo/structures/treap/metas/reverse.hpp

Verified with

• Characteristic Polynomial (verify/linalg/characteristic.test.cpp)
• Pow of Matrix (Frobenius) (verify/linalg/pow_fast.test.cpp)
• Chromatic Polynomial (verify/math/chromatic_poly.test.cpp)
• Sqrt Mod (verify/number_theory/modsqrt.test.cpp)
• Bell Number (verify/poly/bell.test.cpp)
• Division of Polynomials (verify/poly/div.test.cpp)
• Exp of Power Series (verify/poly/exp.test.cpp)
• Find Linear Recurrence (verify/poly/find_linrec.test.cpp)
• Polynomial Interpolation (verify/poly/inter.test.cpp)
• Polynomial Interpolation (Geometric Sequence) (verify/poly/inter_geo.test.cpp)
• Inv of Power Series (verify/poly/inv.test.cpp)
• Inv of Polynomials (verify/poly/inv_mod.test.cpp)
• Consecutive Terms of Linear Recursion (verify/poly/linrec_consecutive.test.cpp)
• Kth term of Linearly Recurrent Sequence (verify/poly/linrec_single.test.cpp)
• Log of Power Series (verify/poly/log.test.cpp)
• Multipoint Evaluation (verify/poly/multieval.test.cpp)
• Multipoint Evaluation (Geometric Sequence) (verify/poly/multieval_geo.test.cpp)
• Conversion to Newton Basis (verify/poly/newton.test.cpp)
• Pow of Power Series (verify/poly/pow.test.cpp)
• Product of Polynomial Sequence (verify/poly/prod_sequence.test.cpp)
• Polynomial Root Finding (verify/poly/roots.test.cpp)
• Shift of Sampling Points of Polynomial (verify/poly/sampling.test.cpp)
• Sqrt of Power Series (verify/poly/sqrt.test.cpp)
• $\sum\limits_{i=0}^\infty r^i i^d$ (verify/poly/sum_exp_poly.test.cpp)
• Polynomial Taylor Shift (verify/poly/taylor.test.cpp)
• Range Affine Range Sum (verify/structures/segtree/range_affine_range_sum.test.cpp)
• Dynamic Range Affine Range Sum (verify/structures/treap/dynamic_sequence_range_affine_range_sum.test.cpp)
• Range Reverse Range Sum (verify/structures/treap/range_reverse_range_sum.test.cpp)

Code

#ifndef CP_ALGO_MATH_AFFINE_HPP
#define CP_ALGO_MATH_AFFINE_HPP
#include <optional>
#include <utility>
#include <cassert>
#include <tuple>
namespace cp_algo::math {
    // a * x + b
    template<typename base>
    struct lin {
        base a = 1, b = 0;
        std::optional<base> c;
        lin() {}
        lin(base b): a(0), b(b) {}
        lin(base a, base b): a(a), b(b) {}
        lin(base a, base b, base _c): a(a), b(b), c(_c) {}

        // polynomial product modulo x^2 - c
        lin operator * (const lin& t) {
            assert(c && t.c && *c == *t.c);
            return {a * t.b + b * t.a, b * t.b + a * t.a * (*c), *c};
        }

        // a * (t.a * x + t.b) + b
        lin apply(lin const& t) const {
            return {a * t.a, a * t.b + b};
        }

        void prepend(lin const& t) {
            *this = t.apply(*this);
        }

        base eval(base x) const {
            return a * x + b;
        }
    };

    // (ax+b) / (cx+d)
    template<typename base>
    struct linfrac {
        base a, b, c, d;
        linfrac(): a(1), b(0), c(0), d(1) {} // x, identity for composition
        linfrac(base a): a(a), b(1), c(1), d(0) {} // a + 1/x, for continued fractions
        linfrac(base a, base b, base c, base d): a(a), b(b), c(c), d(d) {}

        // composition of two linfracs
        linfrac operator * (linfrac t) const {
            return t.prepend(linfrac(*this));
        }

        linfrac operator-() const {
            return {-a, -b, -c, -d};
        }

        linfrac adj() const {
            return {d, -b, -c, a};
        }
        
        linfrac& prepend(linfrac const& t) {
            t.apply(a, c);
            t.apply(b, d);
            return *this;
        }

        // apply linfrac to A/B
        void apply(base &A, base &B) const {
            std::tie(A, B) = std::pair{a * A + b * B, c * A + d * B};
        }
    };
}
#endif // CP_ALGO_MATH_AFFINE_HPP

#line 1 "cp-algo/math/affine.hpp"


#include <optional>
#include <utility>
#include <cassert>
#include <tuple>
namespace cp_algo::math {
    // a * x + b
    template<typename base>
    struct lin {
        base a = 1, b = 0;
        std::optional<base> c;
        lin() {}
        lin(base b): a(0), b(b) {}
        lin(base a, base b): a(a), b(b) {}
        lin(base a, base b, base _c): a(a), b(b), c(_c) {}

        // polynomial product modulo x^2 - c
        lin operator * (const lin& t) {
            assert(c && t.c && *c == *t.c);
            return {a * t.b + b * t.a, b * t.b + a * t.a * (*c), *c};
        }

        // a * (t.a * x + t.b) + b
        lin apply(lin const& t) const {
            return {a * t.a, a * t.b + b};
        }

        void prepend(lin const& t) {
            *this = t.apply(*this);
        }

        base eval(base x) const {
            return a * x + b;
        }
    };

    // (ax+b) / (cx+d)
    template<typename base>
    struct linfrac {
        base a, b, c, d;
        linfrac(): a(1), b(0), c(0), d(1) {} // x, identity for composition
        linfrac(base a): a(a), b(1), c(1), d(0) {} // a + 1/x, for continued fractions
        linfrac(base a, base b, base c, base d): a(a), b(b), c(c), d(d) {}

        // composition of two linfracs
        linfrac operator * (linfrac t) const {
            return t.prepend(linfrac(*this));
        }

        linfrac operator-() const {
            return {-a, -b, -c, -d};
        }

        linfrac adj() const {
            return {d, -b, -c, a};
        }
        
        linfrac& prepend(linfrac const& t) {
            t.apply(a, c);
            t.apply(b, d);
            return *this;
        }

        // apply linfrac to A/B
        void apply(base &A, base &B) const {
            std::tie(A, B) = std::pair{a * A + b * B, c * A + d * B};
        }
    };
}

#ifndef CP_ALGO_MATH_AFFINE_HPP
#define CP_ALGO_MATH_AFFINE_HPP
#include <optional>
#include <utility>
#include <cassert>
#include <tuple>
namespace cp_algo::math{template<typename base>struct lin{base a=1,b=0;std::optional<base>c;lin(){}lin(base b):a(0),b(b){}lin(base a,base b):a(a),b(b){}lin(base a,base b,base _c):a(a),b(b),c(_c){}lin operator*(const lin&t){assert(c&&t.c&&*c==*t.c);return{a*t.b+b*t.a,b*t.b+a*t.a*(*c),*c};}lin apply(lin const&t)const{return{a*t.a,a*t.b+b};}void prepend(lin const&t){*this=t.apply(*this);}base eval(base x)const{return a*x+b;}};template<typename base>struct linfrac{base a,b,c,d;linfrac():a(1),b(0),c(0),d(1){}linfrac(base a):a(a),b(1),c(1),d(0){}linfrac(base a,base b,base c,base d):a(a),b(b),c(c),d(d){}linfrac operator*(linfrac t)const{return t.prepend(linfrac(*this));}linfrac operator-()const{return{-a,-b,-c,-d};}linfrac adj()const{return{d,-b,-c,a};}linfrac&prepend(linfrac const&t){t.apply(a,c);t.apply(b,d);return*this;}void apply(base&A,base&B)const{std::tie(A,B)=std::pair{a*A+b*B,c*A+d*B};}};}
#endif

#line 1 "cp-algo/math/affine.hpp"
#include <optional>
#include <utility>
#include <cassert>
#include <tuple>
namespace cp_algo::math{template<typename base>struct lin{base a=1,b=0;std::optional<base>c;lin(){}lin(base b):a(0),b(b){}lin(base a,base b):a(a),b(b){}lin(base a,base b,base _c):a(a),b(b),c(_c){}lin operator*(const lin&t){assert(c&&t.c&&*c==*t.c);return{a*t.b+b*t.a,b*t.b+a*t.a*(*c),*c};}lin apply(lin const&t)const{return{a*t.a,a*t.b+b};}void prepend(lin const&t){*this=t.apply(*this);}base eval(base x)const{return a*x+b;}};template<typename base>struct linfrac{base a,b,c,d;linfrac():a(1),b(0),c(0),d(1){}linfrac(base a):a(a),b(1),c(1),d(0){}linfrac(base a,base b,base c,base d):a(a),b(b),c(c),d(d){}linfrac operator*(linfrac t)const{return t.prepend(linfrac(*this));}linfrac operator-()const{return{-a,-b,-c,-d};}linfrac adj()const{return{d,-b,-c,a};}linfrac&prepend(linfrac const&t){t.apply(a,c);t.apply(b,d);return*this;}void apply(base&A,base&B)const{std::tie(A,B)=std::pair{a*A+b*B,c*A+d*B};}};}

Back to top page