主題

ZeroJudge - f369: Morty的函數 解題心得

Not In My Back Yard | 2021-01-27 00:00:08

題目連結:


題目大意:
輸入第一列給定一正整數 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 這種輸出。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。
77 巴幣: 100

創作回應

相關創作

更多創作