10268 498-bis

必考題目之一

題目連結

在「線上評測系統問題集存檔」中，我找到了一個非常有趣的問題編號 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';
  }
}