拉格朗日插值法 小结
拉格朗日插值法是干啥的
用来合理的解释你按规律填数乱填的答案
给定n个点\((x_i,y_i)\),求一个n-1次多项式经过这n个点。
算法流程
考虑把这个多项式\(f(x)\)拆成n个多项式\(f_i(x)\),使得第i个多项式在\(j=i\)时,\(f_i(x_j)=1\),并且在$j= i \(时,\)f_i(x_j)=0\(。那么\)f(x)=y_if_i(x)$
首先由于\(j\not=i\)时\(f_i(x_j)=0\),那么\(f_i(x)\)有一个\((x-x_j)\)因子。设\(f_i(x)=\prod\limits_{j\not =i}(x-x_j)s\)
由于\(j=i\)时\(f_i(x_j)=1\),那么\(s=\frac{1}{\prod\limits_{j\not =i}(x_i-x_j)}\)。
也就是说,\(f_i(x)=\prod\limits_{j\not=i}\frac{x-x_j}{x_i-x_j}\),\(f(x)=\sum\limits_i (y_i\prod\limits_{j\not=i}\frac{x-x_j}{x_i-x_j})\)。
这个显然是n-1次的。
实现
如果你需要插出一个x位置的值,很方便做到\(O(n^2)\),如果需要插出这个多项式?
\(\prod\limits_{j\not =i} (x-x_j)\) 不是要\(O(n^2)\)乘?
可以先\(O(n^2)\)算出\(g(x)=\prod (x-x_i)\),然后每次计算\(\frac{g(x)}{(x-x_i)}\)只要\(O(n)\)。还是\(O(n^2)\)。
如果\(x_i=i\)?分母部分可以先预处理阶乘逆元,分子部分可以拆成两部分相乘,就只需要\(O(n)\)了。当然\(f(x)\)在\(x\le n\)要特判。插出多项式?不会。
例题
涂色
有一个长度为n的序列初始全为白色,进行k次操作,每次随机选两个点将它们之间染黑。
求期望被染黑的点数。\(n\le 10^9,k\le 10^3\)(其实可以\(k\le 10^6\))
根据期望的线性性,可以分开算每个点被染黑的概率(答案就是每个点被染黑概率的和
第i个点染黑的概率\(=1-(\)单次没染黑的概率\()^k\)
单次没染黑的概率显然\(= \frac{(i-1)^2+(n-i)^2}{n^2}\)
那么答案就是\(n-\frac{\sum\limits_{i=1}^n((i-1)^2+(n-i)^2)^k}{n^{2k}}\)
设\(f(x)=\sum\limits_{i=1}^x((i-1)^2+(n-i)^2)^k\)。
这东西看上去是\(2k+1\)次的(x个2k次的多项式和?)
然后就可以先算x=1到2k+2的\(f(x)\),然后拉格朗日插值算出\(f(n)\)。时间复杂度\(O(k\log k)\)(2k+2次计算每次需要\(O(\log k)\))
CF622F
求\(\sum\limits_{i=1}^ni^k\),其中\(k\le 10^6,n\le 10^9\),输出对1e9+7取膜。
设这个为\(f(n)\)
这个看上去是一个k+1次多项式(n个k次的和?)
那就先算\(f(1)..f(k+2)\),然后插值。时间复杂度\(O(k\log k)\)。