#pragma once
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

template <typename T>
class Polinom {
private:
	int n;
	T *koef;
	template <typename T> friend  ostream& operator << (ostream &, const Polinom<T> &);	// перегрузка вывода
public:
	Polinom() {};
	Polinom(T c); // конструктор с 1 коэф
	Polinom(T *a, int size); // конструктор с массивом коэф
	Polinom(Polinom<T> &p); // конструктор копирования
	~Polinom(); // деструктор
	Polinom operator + (Polinom<T> &p);
	Polinom operator - (Polinom<T> &p);
	Polinom operator * (Polinom<T> &p);

	Polinom operator *=(Polinom<T> &p);
	Polinom operator -=(Polinom<T> &p);
	Polinom operator +=(Polinom<T> &p);
	bool operator ==(Polinom<T> &p);
	bool operator !=(Polinom<T> &p);
	T operator () (T x);
};

template <typename T>
Polinom<T>::Polinom(T c)
{
	n = 1;
	koef = new T[n];
	koef[0] = c;
}

template <typename T>
Polinom<T>::Polinom(T *a, int sz)
{
	n = sz;
	koef = new T[n];
	for (int i = 0; i<n; i++)
		koef[i] = a[i];
}

template <typename T>
Polinom<T>::Polinom(Polinom<T> &p)
{
	n = p.n;
	koef = new T[n];
	for (int i = 0; i<n; i++)
		koef[i] = p.koef[i];
}

template <typename T>
Polinom<T>::~Polinom()
{
	delete[]koef;
}


template <typename T>
ostream& operator <<(ostream &out, const Polinom<T> &p)
{
	bool has = false;
	for (int i = p.n - 1; i >= 0; i--)
	{
		T kf = p.koef[i];
		if (kf < 0)
		{
			if (kf != -1 || i == 0)
			{

				out << kf;
				if (i > 0)
				{
					out << "*x";
					if (i>1)
						out << "^(" << i << ")";
				}
				has = true;

			}
			else
			{
				out << '-';
				if (i > 0)
				{
					out << "x";
					if (i>1)
						out << "^(" << i << ")";
				}
				has = true;

			}
		}
		else
			if (kf > 0)
			{
				if (has)
				{
					out << "+";
					has = true;
				}
				if (kf > 1 || i == 0)
				{
					out << kf;
					if (i > 0)
					{
						out << "*x";
						if (i>1)
							out << "^(" << i << ")";
					}
					has = true;
				}
				else
				{
					if (i > 0)
					{
						out << "x";
						if (i>1)
							out << "^(" << i << ")";
					}
					has = true;
				}

			}
	}
	if (!has)
		out << 0;
	out << endl;
	return out;
}

template <typename T>
Polinom<T> Polinom<T>::operator +(Polinom<T> &p)
{
	int newn = max(n, p.n);
	Polinom<T> res = Polinom<T>();
	res.n = newn;
	res.koef = new T[n];
	for (int i = 0; i < newn; i++)
	{
		T x = 0;
		if (i < n)
			x = koef[i];
		T y = 0;
		if (i < p.n)
			y = p.koef[i];
		res.koef[i] = x + y;
	}
	return res;
}

template <typename T>
Polinom<T>Polinom<T>::operator -(Polinom<T> &p)
{
	int newn = max(n, p.n);
	Polinom res = Polinom();
	res.n = newn;
	res.koef = new T[n];
	for (int i = 0; i < newn; i++)
	{
		T x = 0;
		if (i < n)
			x = koef[i];
		T y = 0;
		if (i < p.n)
			y = p.koef[i];
		res.koef[i] = x - y;
	}
	return res;
}

template <typename T>
Polinom<T>Polinom<T>::operator *(Polinom<T> &p)
{
	int newn = n + p.n-1;
	Polinom res = Polinom();
	res.n = newn;
	res.koef = new T[newn];
	for (int i = 0; i < newn; i++)
		res.koef[i] = 0;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j<p.n; j++)
			res.koef[i+j] += koef[i]*p.koef[j];
	}
	return res;
}

template <typename T>
Polinom<T> Polinom<T>::operator *=(Polinom<T> &p)
{
	int newn = n + p.n - 1;
	Polinom  res = Polinom();
	res.n = newn;
	res.koef = new T[newn];
	for (int i = 0; i < newn; i++)
		res.koef[i] = 0;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j<p.n; j++)
			res.koef[i + j] += koef[i] * p.koef[j];
	}
	delete[]this->koef;
	n = newn;
	koef = new T[n];
	for (int i = 0; i < n; i++)
		koef[i] = res.koef[i];
	return *this;
}

template <typename T>
Polinom<T> Polinom<T>::operator -=(Polinom<T> &p)
{
	int newn = max(n, p.n);
	Polinom res = Polinom();
	res.n = newn;
	res.koef = new T[newn];
	for (int i = 0; i < newn; i++)
	{
		T x = 0;
		if (i < n)
			x = koef[i];
		T y = 0;
		if (i < p.n)
			y = p.koef[i];
		res.koef[i] = x - y;
	}
	delete [] this->koef;
	n = newn;
	koef = new T[n];
	for (int i = 0; i < n; i++)
		koef[i] = res.koef[i];
	return *this;
}

template <typename T>
Polinom<T> Polinom<T>::operator +=(Polinom<T> &p)
{
	int newn = max(n, p.n);
	Polinom res = Polinom();
	res.n = newn;
	res.koef = new T[newn];
	for (int i = 0; i < newn; i++)
	{
		T x = 0;
		if (i < n)
			x = koef[i];
		T y = 0;
		if (i < p.n)
			y = p.koef[i];
		res.koef[i] = x + y;
	}
	delete []this->koef;
	n = newn;
	koef = new T[n];
	for (int i = 0; i < n; i++)
		koef[i] = res.koef[i];
	return this;
}

template <typename T>
bool Polinom<T>::operator ==(Polinom<T> &p)
{
	for (int i = 0; i < max(n, p.n); i++)
	{
		T x = 0;
		if (i < n)
			x = koef[i];
		T y = 0;
		if (i < p.n)
			y = p.koef[i];
		if (x != y)
			return false;
	}
	return true;
}

template <typename T>
bool Polinom<T>::operator !=(Polinom<T> &p)
{
	return !(this == p);
}

template <typename T>
T Polinom<T>::operator () (T x)
{
	T ans = 0;
	T pow = 1;
	for (int i = 0; i < n; i++,pow*=x)
	{
		ans += pow*koef[i];
	}
	return ans;
}