2020-2021:teams:legal_string:jxm2001:多项式_1
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:多项式_1 [2020/08/03 22:44] jxm2001 |
2020-2021:teams:legal_string:jxm2001:多项式_1 [2020/08/03 22:45] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 130: | 行 130: | ||
| 易知 $\sum_{j=i+1}^{2i-1}j^k$ 是 $k+1$ 次多项式，于是 $\sum_{i=2}^n\sum_{j=i+1}^{2i-1}j^k$ 是 $k+2$ 次多项式。 | 易知 $\sum_{j=i+1}^{2i-1}j^k$ 是 $k+1$ 次多项式，于是 $\sum_{i=2}^n\sum_{j=i+1}^{2i-1}j^k$ 是 $k+2$ 次多项式。 | ||
| - | 线性筛预处理 $1^k,2^k\cdots (k+3)^k$，于是可以线性时间求出 $f(1),f(2)\cdots f(k+3)$，最后考虑拉格朗日插值即可。 | + | 线性筛预处理 $1^k,2^k\cdots (2k+5)^k$，于是可以线性时间求出 $f(1),f(2)\cdots f(k+3)$，最后套用拉格朗日插值法即可。 |
| 总时间复杂度 $O(k)$。 | 总时间复杂度 $O(k)$。 | ||
2020-2021/teams/legal_string/jxm2001/多项式_1.1596465886.txt.gz · 最后更改: 2020/08/03 22:44 由 jxm2001
