あたまわるいので・・・
この問題な
こいつのせいで丸２日間、作業が一切滞った
これだからキョーギプログラミングはね…（無限に時間が溶ける…）
自己解決は諦めておとなしく解決方法晒してるやつ見てきた
手順しか書かれてなくて
察するに、微分
D階導関数は定数項だけになるわけで
要するに差分の差分の差分の差分の…を取ってくれば求まるということらしいが
P(n)=a4*n^4+a3*n^3+a2*n^2+a1*n+a0 P'(n)=4*a4*n^3+3*a3*n^2+2*a2*n+a1 P''(n)=12*a4*n^2+6*a3*n+2*a2 P'''(n)=24*a4*n+6*a3 P''''(n)=24*a4
こんな感じ？(わからん)
差分を取ってるだけだから、差分から差分を生成して…を繰り返して出てくるのは整数になるわけで、そうなんだろうけど
これが次数が最小のものであることの証明はわからんし知らんし、謎
(まぁ一応説明どおりのコード書いてサンプルケースが合うことは確認したが)
問題の答えにならんけど
最小でないものであれば
(S+C)次多項式とするとC個の整数はテキトーに選んでも成立するって感じぽい
(C個をテキトーな数字にして(S+C)個の(S+C)次多項式として連立方程式として解く事ができるぽい)
例えば入力が (S=3, C=2, Xi=[2, 7, 18]) でC個(2個)を[-5,11]とかにして
P(1) = 2 = a5*1^5 + a4*1^4 + a3*1^3 + a2*1^2 + a1*1^1 + a0*1^0 P(2) = 7 = a5*2^5 + a4*2^4 + a3*2^3 + a2*2^2 + a1*2^1 + a0*2^0 P(3) = 18 = a5*3^5 + a4*3^4 + a3*3^3 + a2*3^2 + a1*3^1 + a0*3^0 P(4) = -5 = a5*4^5 + a4*4^4 + a3*4^3 + a2*4^2 + a1*4^1 + a0*4^0 P(5) = 11 = a5*5^5 + a4*5^4 + a3*5^3 + a2*5^2 + a1*5^1 + a0*5^0
これを連立して解くとこんな感じ？
a0=156/1 a1=-1251/4 a2=4987/24 a3=-215/4 a4=113/24 a5=0
