簡易多項式。計算速度とか精度とか気にしない

polynomial.hpp

#include<array>

template<class T, std::size_t N>
class Polynomial
{
	std::array<T, N + 1> data;
	using value_type = T;
public:
	template<class T,class ...U>
	Polynomial(T x, U ...y)
		:data({ x, y... })
	{}
	Polynomial()
	{
		data.fill(value_type{ 0 });
	}
	//コンテナサイズ
	inline std::size_t size()const
	{
		return data.size(); 
	}

	//最高字数計測
	std::size_t countOrder()const
	{
		for (std::size_t n = size() - 1; n > 0; --n)
		{
			if ((*this)[n] != 0)
				return n;
		}
		return 0;
	}

	//アクセッサ
	inline value_type & operator[](std::size_t n)
	{
		return data[n];
	}
	inline value_type const& operator[](std::size_t n)const
	{
		return data[n];
	}
	inline value_type & at(std::size_t n)
	{
		return data.at(n);
	}
	inline value_type const& at(std::size_t n)const
	{
		return data.at(n);
	}

	//F*x
	Polynomial upshift(std::size_t n)const
	{
		if (n == 0)return *this;
		Polynomial temp;
		for (std::size_t i = 0; i < size() - n; ++i)
		{
			temp[i + n] = (*this)[i];
		}
		return temp;
	}

	//定数倍
	Polynomial multScala(value_type const&c)const
	{
		Polynomial temp;
		for (std::size_t i = 0; i < size(); ++i)
		{
			temp[i] = (*this)[i] * c;
		}
		return temp;
	}

	//微分
	Polynomial diff()const
	{
		Polynomial temp;
		for (std::size_t i = 1; i < size(); ++i)
		{
			temp[i - 1] = (*this)[i] * i;
		}
		return temp;
	}

	Polynomial operator + ()
	{
		return *this;
	}
	Polynomial operator - ()
	{
		return multScala(-1);
	}
	
	Polynomial& operator += (Polynomial const&rhs)
	{
		for (std::size_t n = 0; n < size(); ++n)
		{
			(*this)[n] += rhs[n];
		}
		return *this;
	}
	inline Polynomial operator+(Polynomial const&rhs)const
	{
		return Polynomial(*this) += rhs;
	}

	Polynomial& operator -= (Polynomial const&rhs)
	{
		for (std::size_t n = 0; n < size(); ++n)
		{
			(*this)[n] -= rhs[n];
		}
		return *this;
	}
	inline Polynomial operator-(Polynomial const&rhs)const
	{
		return Polynomial(*this) -= rhs;
	}

	Polynomial operator * (Polynomial const&rhs)const
	{
		Polynomial temp;
		for (std::size_t n = 0; n < size(); ++n)
		{
			for (std::size_t i = 0; i < n; ++i)
			{
				temp[n] = (*this)[i] * (*this)[n - i];
			}
		}
		return temp;
	}
	inline Polynomial& operator *= (Polynomial const&rhs)
	{
		return *this = (*this) * rhs;
	}

	Polynomial operator/(Polynomial const&rhs)const
	{
		auto lhs = *this;
		auto lo = lhs.countOrder();
		auto ro = rhs.countOrder();
		if (lo < ro)return Polynomial{};

		auto dif = lo - ro;
		Polynomial temp;
		for (std::size_t i = 0; i < dif + 1; ++i)
		{
			temp[dif - i] = lhs[lo - i] / rhs[ro];
			lhs -= rhs.upshift(dif - i).multScala(temp[dif - i]);
		}
		return temp;
	}
	inline Polynomial& operator /= (Polynomial const&rhs)
	{
		return *this = (*this) / rhs;
	}

	Polynomial& operator%=(Polynomial const&rhs)
	{
		auto lo = countOrder();
		auto ro = rhs.countOrder();
		if (lo < ro)return *this;
		auto dif = lo - ro;

		for (std::size_t i = 0; i < dif + 1; ++i)
		{
			auto r = (*this)[lo - i] / rhs[ro];
			*this -= rhs.upshift(dif - i).multScala(r);
		}
		return *this;
	}
	inline Polynomial operator%(Polynomial const&rhs)const
	{
		return Polynomial(*this) %= rhs;
	}
};


template <class charT, class traits, class T,std::size_t N>
std::basic_ostream<charT, traits>& operator << (std::basic_ostream<charT, traits>& os, const Polynomial<T, N>& poly)
{
	os << "{ ";
	auto order = poly.countOrder() + 1;
	for (std::size_t i = 0; i < order; ++i)
	{
		if (i) os << " + ";
		os << poly[i];
		if (i) os << "x^" << i ;
	}
	os << " }";
	return os;
}