必考題目之一

題目連結

在「線上評測系統問題集存檔」中，我找到了一個非常有趣的問題編號 498，標題為「Polly the Polynomial」。說實話，我並未解出它，但我從它衍生出這個問題。

本題所有內容皆源自 498 題。特別地，498 題是「…旨在幫助你記住…基礎代數技巧，讓世界變得更美好，諸如此類。」本題的設計也是為了幫助你回憶基礎微分代數技巧，加快世界變得更美好的速度，等等。

在 498 題中，你需要計算以下多項式的值：

a₀ xⁿ + a₁ xⁿ⁻¹ + … + aₙ₋₁ x + aₙ

在本題中，你需要計算其導函數。請記住導函數定義為：

a₀·n xⁿ⁻¹ + a₁·(n−1) xⁿ⁻² + … + aₙ₋₁

所有輸入及輸出資料皆可存放於整數中，其絕對值小於 2³¹。

輸入格式

你的程式應接受偶數行的文字輸入。每兩行代表一個測資。

• 第一行包含一個整數，表示 x 的值。
• 第二行包含一串整數 a₀, a₁, …, aₙ₋₁, aₙ，代表一組多項式係數。

輸入以 EOF 結尾。

輸出格式

對於每組測資，計算給定 x 值下多項式的導函數，並將結果輸出於單行。

解題思路

使用 stringstream 來分割成整數陣列
之後使用 霍納法 計算多項式的導函數在指定 x 的值 詳情請閱讀程式碼

程式碼

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s; int x, n;
    while (cin >> x) { // 讀取輸入，直到檔案結尾
        cin.ignore(); // 跳過 x 後面的換行字符 '\n'，確保接下來的 getline 能夠正確執行
        getline(cin, s); // 讀取一整行數字 (係數)
        stringstream ss(s); // 將字串導入 stringstream
        vector<int> v; // 宣告儲存多項式係數的陣列
        while (ss >> n) v.push_back(n); // 從字串中分割出係數放入陣列中
        v.pop_back(); // 常數項的導數為 0，不用計算

        int sum = 0;
        n = v.size(); // 將陣列長度存進 n，避免迴圈在每次判斷時需要重複計算陣列長度
        for (int i = 0; i < n; i++) {
            sum *= x; // 將累積結果乘上 x，符合該係數降冪後的 x 次方 (越早放入的係數會乘上相應次數)
            sum += v[i]*(n-i); // 將當前項的係數與其對應階數相乘後累加
        }
        cout << sum << '\n';
    }
}