alan23273850 的刷題筆記
d437: 10326 - The Polynomial Equation
Tags: polynomial
出處：https://zerojudge.tw/ShowProblem?problemid=d437
提交：https://zerojudge.tw/Submissions?problemid=d437&account=allllllan123456
問題：給定一個多項式 = 0 的根至多 50 個，請印出此多項式 (各個次方項的係數)。
解法：其實很簡單，只要從初始多項式 1 開始依序乘上每個 $x - r_i$，其中 $r_i$ 代表多項式的一個根，最後就是答案。過程中只要隨時維護暫存結果多項式的每個係數即可，另外我們也知道乘法的運算其實可以由右 (低次項) 到左 (高次項) 依序 in-place 地填表：$$\Big(\text{co}[0]\cdot x^n + \text{co}[1]\cdot x^{n-1} + … + \text{co}[n-1]\cdot x + \text{co}[n]\Big)\cdot(x-r_i)\\ = \text{co}[0]\cdot x^{n+1} + \Big(\text{co}[1]-r_i\cdot\text{co}[0]\Big)\ x^n + … + \Big(\text{co}[n]-r_i\cdot\text{co}[n-1]\Big)\ x - r_i\cdot\text{co}[n]\\ = \text{co'}[0]\cdot x^{n+1} + \text{co'}[1]\cdot x^n + … + \text{co'}[n]\cdot x + \text{co'}[n+1]$$ 除了首項和末項之外，其他項的係數規則皆相同，所以其實每次陣列最左邊元素的值都是 1，而最右邊每次都會長出一個新的常數，總共時間複雜度便是 $\mathcal O(N^2)$，但空間只需要 $\mathcal O(N)$，其中 $N$ 是根的數量。
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
5 int N, r, coL; long long co[51] = {1};
6 while (cin >> N) {
7 coL = 1;
8 while (N--) {
9 cin >> r; r = -r;
10 co[coL] = r * co[coL-1];
11 for (int i=coL-1; i>0; i--)
12 co[i] += co[i-1] * r;
13 coL++;
14 }
15 for (int i=0; i<coL; i++) { /* power = coL-1 - i; */
16 if (co[i] < 0) cout << " - ";
17 else if (i==coL-1 || i>0 && co[i]>0) cout << " + ";
18 if (i==coL-1 || abs(co[i])>1) cout << abs(co[i]);
19 if (coL-1-i>0 && co[i]) {
20 cout << 'x';
21 if (coL-1 - i > 1)
22 cout << '^' << coL-1 - i;
23 }
24 }
25 cout << " = 0\n";
26 }
27 return 0;
28}