これ、蟻本とかにも書かれているので常識かなと思ってたんですが、最近よくハマっている人を見かけるので、記事として書いておくことにします。 ↓ 追記 ↓ この記事と別の手法についても書きました。競プロの範囲ではどちらの手法でも困らない気もしますが、…

問題設定 たかだか \(n\) 次式 \(f(x) = \sum_{i=0}^n a_i x^i\) がありますが、与えられません。 \(n+1\) 個の点 \(x_0, x_1, \dots, x_n\) と、それらの点での \(f\) の値 \(y_0, y_1, \dots, y_n\) が与えられます。 すなわち、\(y_i = f(x_i)\) (\(i=0, …

問題設定 多項式 \(f(x) = \sum_{i=0}^n a_i x^i\) と、\(m\) 個の異なる点 \(x_0, x_1, \dots, x_{m -1}\) が与えられます。 これらの点での値 \(f(x_0), f(x_1), \dots, f(x_{m -1})\) を求めてください。 ただし、各計算は \(998244353 = 119\cdot 2^{23}…