# 題目: 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";
	}
	}