Skip to content
XCPC Notes
搜索
K
Main Navigation
首页
算法模板
知识点
竞赛题解
Appearance
Menu
Return to top
本页目录
发布时间：2024-07-31
重心拉格朗日插值法
g
=
∏
i
=
0
n
k
−
x
i
,
t
i
=
y
i
∏
x
i
−
x
j
g=\prod _{i=0}^nk-x_i,t_i=\frac{y_i}{\prod x_i-x_j}
g
=
∏
i
=
0
n
k
−
x
i
,
t
i
=
∏
x
i
−
x
j
y
i
f
(
k
)
=
g
∑
i
=
0
n
t
i
k
−
x
i
f(k)=g \sum_{i=0}^n\frac{t_i}{k-x_i}
f
(
k
)
=
g
∑
i
=
0
n
k
−
x
i
t
i
每新加入一个点只需要计算
t
i
t_i
t
i
即可，预处理仍然是
O
(
n
2
)
O(n^2)
O
(
n
2
)
,但是插入是
O
(
n
)
O(n)
O
(
n
)
的
