题目大意: 给出(n)个点(P_i(x_i,y_i)),讲过这(n)个点的最多(n - 1)次的多项式记为(f(x)),求(f(k))的值
方法一:差分法
差分法适用于(x_i = i)的情况
如,用差分法求(f(x) = sum_{i = 1}^xi^2)的多项式形式。
1 5 14 30 55 91
4 9 16 25 36
5 7 9 11
2 2 2
第一行为(f(x))的连续的前几项。
若上面一行有(n)个值,下面一行有(n - 1)个值,每个值为上面对应的相邻两项的差。观察到,如果这样操作的次数足够多(前提是(f(x))为多项式),每次总会返回一个定值,可以利用这个定制求出(f(x))的每一项的系数,然后即可将(k)带入多项式中求解。
如上例中可求出(f(x) = frac{1}{3}n^3+frac{1}{2}n^2+frac{1}{6}n)。时间复杂度为(O(n^2)),对给出的点的限制性较强。
方法二:高斯消元
使用待定系数法。设(f(x) = sum_{i = 0}^{n-1}a_ix^i)将每个(x_i)代入(f(x)),有(f(x_i)=y_i),这样就可以得到一个由(n)条(n)元(1)次方程所组成的方程组,然后使用高斯消元求出每一项(a_i),然后将(k),代入求值。
时间复杂度(O(n^3)),对给出点的坐标无要求。
方法三: 拉格朗日插值法
考虑将每个点做一个对于(x)轴的垂线,设垂足为(H_i(x_i,0))。
如上图所示,黑线等于蓝线加绿线加红线。每次我们选择一个(P_i),并选择其他的(H_j[j ot=i]),做一条过这些点的一条至多(n-1)次的线。由于有(n-2)个点都在(x)轴上,我们知道这条线的解析式一定是形如
最后将所有的(g(x))相加,即(f(x)=sum_{i=1}^ng_i(x))。因为对于每个点(P_i),都只有一条函数经过(P_i),其余都经过(H_i),这一项的系数是(0),所以最后的和函数总是过所有(n)个点的。
公式整理得:
如果要将每一项都算出来,时间复杂度仍是(O(n^2))的,但是本题中只用求出(f(k))的值,所以只需将(k)代入进式子里得到:
本题中,还需要求解逆元。如果先分贝计算出分子和分母,再将分子乘进分母的逆元,累加进最后的答案,时间复杂度的瓶颈就不会在求解逆元上,时间复杂度为(O(n^2))。