Solution Idea

50021. Polynomial

不負責任的中文翻譯 by Morris

題目描述

實作一個 $x$ 的整數係數多項式結構,必須儲存每一項的係數,假設最高位為 4095,意即 $x^{4095}$,因此需要儲存 4096 項的係數。

  • void init(Polynomial *poly, int coefficient[], int n);
    初始化多項式,將傳入的 int coefficient[] 的前 $n$ 項,儲存到 Polynomial *poly 所指向的記憶體位置。如 coefficient[] = {1, 3, 2}, n = 3,相當於初始化 $2x^2 + 3x + 1$。

  • Polynomial add(Polynomial *poly1, Polynomial *poly2);
    把兩個多項式相加後回傳,例如 $\text{poly1} = x^2 + 1, \; \text{poly2} = x^3 + 2$,最後回傳 $x^3 + x^2 + 3$。

  • Polynomial multiply(Polynomial *poly1, Polynomial *poly2);
    將兩個多項式相乘後回傳,例如 $\text{poly1} = x^2 + 1, \; \text{poly2} = x^3 + 2$,最後回傳 $(x^2 + 1)( x^3 + 2) = x^5 + x^3 + 2x^2 + 2$。

  • void print(Polynomial *poly);
    打印出 Polynomial *poly 儲存的內容,若係數為 0 則不用輸出。特別小心 +3x 不應該輸出成 +3x^1,而在常數項並應該輸出 +5x^0,應直接輸出 +5。你可以使用 printf("%+d", coef[i]) 減少正號的判斷。

乘法加速

若多項式高次係數都為 0,則記錄最高的非 0 係數為何。在實作乘法部份,兩個多項式的最高係數分別為 $n, \; m$,只需要 $\mathcal{O}(nm)$,而不是計算 $(0 x^{4095} + 0 x^{4094} + \cdots + 0 x^ 3 + x^2 + 1)(0 x^{4095} + 0 x^{4094} + \cdots + 0 x^ 4 + x^3 + 2) = x^5 + x^3 + 2x^2 + 2$,這麼寫會變成 $\mathcal{O}(4096^2)$。

更完美的境界:表示 $f(x) = 3x^4 - x^2 + 5$ 時,輸出 3x^4-x^2+5 而非 +3x^4-1x^2+5。此外,若多項式為 $f(x) = 0$,應輸出 0,而非一行空行。這都是非常 tricky 的部份,前述不在這次的處理範圍內。

Discussion