題目連結：
題目大意：
輸入第一列給定一正整數 t （t < 1048576），代表有 t 筆測試資料，每筆佔四列。
測資第一列給定一非負整數 n （0 ≦ n ≦ 4），代表一個 n 次方函數 f(x)。
測資第二列給定 n + 1 個整數，代表 x1 、 x2 、 …… 、 xn+1 （|xi| ≦ 1000），第三列給定 n + 1 個整數，代表 f(x1) 、 f(x2) 、 …… 、 f(xn+1) 之值（|f(xi)| ≦ 1000）。
測資最後一列給定一整數 k （|k| ≦ 1000），試問 f(k) ÷ 100 整數部分之值為何？
範例輸入：
5
4
736 581 1000 941 864
265 -574 -897 135 610
-889
3
-988 795 721 -99
125 281 619 -754
-860
3
818 -329 800 -192
-383 382 -153 514
-842
0
-270
701
660
4
965 -195 600 723 -180
617 -590 -298 -54 575
833
範例輸出：
-7034
-8
44
7
5
解題思維：
比較好實作的插值法應該會是拉格朗日插值法（Lagrange Interpolation）。
因為多項次為 n 次方，所以插值法會有 n + 1 項（以下定為 P(xi)）。根據拉格朗日插值法：
這樣就可以看到當代入 x = xj （j ≠ i）時，P(xi) 這項會等於 0。而代入 x = xi 時，分數上下會相等所以會變為 1 × f(xi) = f(xi) ，而其它項因為前面的原因而為 0，所以整體為 f(xi)。
而 f(x) = P(x1) + P(x2) + …… + P(xn+1)。因此我們便得到了原本的多項式 f(x) （雖然樣子看起來很奇妙），接著就把 k 代入進去即可得到 f(k)。
但是因為題目要求 f(k) ÷ 100 的整數部分，所以記得將 f(k) 除以 100 然後截掉小數部分（例如使用 trunc() 函式等），但是記得不應出現 -0 這種輸出。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
達人
