# 題目: UVa 10326 - The Polynomial Equation

# 題目說明

給你一個方程式的n組解，求此方程式展開的樣子

---

INPUT:
輸入一個整數n，代表方程式有n組解
接下來輸入n個整數，各代表一組解
直到EOF結束

---

OUTPUT:
輸出展開後的方程式

# 解題方法

假設解為k1, k2, ..., kn，則方程式可以表示成(x - k1) * (x - k2) * ... * (x - kn) = 0
由此可知能透過乘法將方程式展開 (類似於大數乘法)
比較要注意的是這題的輸出格式很複雜

# 參考程式碼

#include <iostream>
#include <vector>

using namespace std;

static auto fast_io = []
{
	ios::sync_with_stdio(false);
	cout.tie(nullptr);
	cin.tie(nullptr);
	return 0;
}();

int main()
{
	int n, num;

	while (cin >> n)
	{
		vector<long long> buf = {1};

		while (n--)
		{
			cin >> num;
			vector<long long> t = { -num, 1 };
			vector<long long> mul(buf.size() + t.size(), 0);

			for (int i = 0; i < buf.size(); ++i)
				for (int j = 0; j < t.size(); ++j)
					mul[i + j] += buf[i] * t[j];

			while (!mul.empty() && mul.back() == 0) mul.pop_back();
			buf = mul;
		}
		
		for (int i = buf.size() - 1; i >= 0; --i)
		{
			if (buf[i] == 0 && i != 0) continue;
			if (i != buf.size() - 1) cout << (buf[i] >= 0 ? " + " : " - ");
			if ((buf[i] != 1 && buf[i] != -1) || i == 0) cout << (buf[i] > 0 ? buf[i] : -buf[i]);
			if (i != 0) cout << "x";
			if (i > 1) cout << "^" << i;		
		}
		cout << " = 0\n";
	}
}