# Untitled

a guest
Oct 13th, 2019
83
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