SHARE
TWEET

Untitled

a guest Oct 13th, 2019 80 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <algorithm>
  2. #include <functional>
  3. #include <iostream>
  4. #include <map>
  5.  
  6. using namespace std;
  7.  
  8. template<typename T>
  9. class Polynomial {
  10.     private:
  11.     vector<T> a;
  12.  
  13.     void clean() {
  14.         while (!a.empty() && a.back() == T(0)) a.pop_back();
  15.     }
  16.  
  17.     public:
  18.     Polynomial(const vector<T>& other): a(other) { clean(); }
  19.  
  20.     Polynomial(T c = T()): a(1, c) { clean(); }
  21.  
  22.     template<typename It>
  23.     Polynomial(It first, It last): a(first, last) { clean(); }
  24.  
  25.     const auto begin() const {
  26.         return a.begin();
  27.     }
  28.  
  29.     auto begin() {
  30.         return a.begin();
  31.     }
  32.  
  33.     const auto end() const {
  34.         return a.end();
  35.     }
  36.  
  37.     auto end() {
  38.         return a.end();
  39.     }
  40.  
  41.     int Degree() const {
  42.         return a.size() - 1;
  43.     }
  44.  
  45.     bool operator==(const Polynomial& other) const {
  46.         return
  47.             Degree() != other.Degree()
  48.             ? false
  49.             : equal(begin(), end(), other.begin(), other.end());
  50.     }
  51.  
  52.     bool operator!=(const Polynomial& other) const {
  53.         return !(*this == other);
  54.     }
  55.  
  56.     const T operator[](int i) const {
  57.         if (i > Degree()) return T(0);
  58.         return a[i];
  59.     }
  60.  
  61.     Polynomial& operator+=(const Polynomial& other) {
  62.         if (Degree() < other.Degree()) a.resize(other.Degree() + 1, T(0));
  63.         size_t min_sz = min(Degree(), other.Degree()) + 1;
  64.         transform(begin(), begin() + min_sz,
  65.                   other.begin(),
  66.                   begin(),
  67.                   plus<T>());
  68.         clean();
  69.         return *this;
  70.     }
  71.  
  72.     Polynomial operator+(const Polynomial& other) const {
  73.         Polynomial tmp(*this);
  74.         tmp += other;
  75.         return tmp;
  76.     }
  77.  
  78.     Polynomial& operator-=(const Polynomial& other) {
  79.         if (Degree() < other.Degree()) a.resize(other.Degree() + 1, T(0));
  80.         size_t min_sz = min(Degree(), other.Degree()) + 1;
  81.         transform(begin(), begin() + min_sz,
  82.                   other.begin(),
  83.                   begin(),
  84.                   minus<T>());
  85.         clean();
  86.         return *this;
  87.     }
  88.  
  89.     Polynomial operator-(const Polynomial& other) const {
  90.         Polynomial tmp(*this);
  91.         tmp -= other;
  92.         return tmp;
  93.     }
  94.  
  95.     Polynomial& operator*=(const Polynomial& other) {
  96.         if (Degree() == -1 || other.Degree() == -1) {
  97.             a.clear();
  98.             return *this;
  99.         }
  100.         vector<T> result(Degree() + other.Degree() + 1, T(0));
  101.         for (int i = 0; i <= Degree(); ++i) {
  102.             for (int j = 0; j <= other.Degree(); ++j) {
  103.                 result[i + j] += (*this)[i] * other[j];
  104.             }
  105.         }
  106.         a = move(result);
  107.         clean();
  108.         return *this;
  109.     }
  110.  
  111.     Polynomial operator*(const Polynomial& other) const {
  112.         Polynomial tmp(*this);
  113.         tmp *= other;
  114.         return tmp;
  115.     }
  116.  
  117.     T operator()(const T& x) const {
  118.         T result = T(0), power = T(1);
  119.         for (int i = 0; i <= Degree(); ++i) {
  120.             result += power * a[i];
  121.             power *= x;
  122.         }
  123.         return result;
  124.     }
  125.  
  126.     Polynomial operator&(const Polynomial& other) const {
  127.         Polynomial result(T(0)), power(T(1));
  128.         for (int i = 0; i <= Degree(); ++i) {
  129.             result += power * (*this)[i];
  130.             power *= other;
  131.         }
  132.         return result;
  133.     }
  134.  
  135.     Polynomial operator/(const Polynomial& other) const {
  136.         Polynomial q(T(0)), r(*this);
  137.         while (r.Degree() != -1 && r.Degree() >= other.Degree()) {
  138.             vector<T> tmp(r.Degree() - other.Degree() + 1, T(0));
  139.             tmp.back() = r[r.Degree()] / other[other.Degree()];
  140.             Polynomial t(tmp);
  141.             q += t;
  142.             r -= t * other;
  143.         }
  144.         return q;
  145.     }
  146.  
  147.     Polynomial operator%(const Polynomial& other) const {
  148.         Polynomial q(T(0)), r(*this);
  149.         while (r.Degree() != -1 && r.Degree() >= other.Degree()) {
  150.             vector<T> tmp(r.Degree() - other.Degree() + 1, T(0));
  151.             tmp.back() = r[r.Degree()] / other[other.Degree()];
  152.             Polynomial t(tmp);
  153.             q += t;
  154.             r -= t * other;
  155.         }
  156.         return r;
  157.     }
  158.  
  159.     Polynomial operator,(const Polynomial& other) const {
  160.         if (other == Polynomial(T(0))) {
  161.             Polynomial result(*this);
  162.             result = result / Polynomial(result[result.Degree()]);
  163.             return result;
  164.         } else {
  165.             Polynomial r = (*this) % other;
  166.             return (other, r);
  167.         }
  168.     }
  169. };
  170.  
  171. template<typename T>
  172. ostream& operator<<(ostream& out, const Polynomial<T>& p) {
  173.     if (p.Degree() == -1) {
  174.         out << T(0);
  175.     } else {
  176.         for (int i = p.Degree(); i >= 0; --i) {
  177.             if (p[i] == T(0)) continue;
  178.  
  179.             if (i != p.Degree() && p[i] > T(0)) {
  180.                 out << '+';
  181.             }
  182.             if (i == 0) {
  183.                 out << p[i];
  184.             } else {
  185.                 if (p[i] != T(1) && p[i] != T(-1)) out << p[i] << '*';
  186.                 if (p[i] == T(-1)) out << '-';
  187.                 out << 'x';
  188.                 if (i != 1) out << '^' << i;
  189.             }
  190.         }
  191.     }
  192.     return out;
  193. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top