给定一个数列的前k项$a_1,\ldots, a_k$，并不足以唯一确定其下一项的值，因为显然有无数个多项式$p(x)$可以满足$n=1,\ldots,k$时$p(n)=a_n$。

例如给定数列的前两项$a_1=1$，$a_2=8$，显然$p(x)=x^3$和$p(x)=7x-6$都满足$p(1)=1$，$p(2)=8$，下一项可以是$27$，也可以是$15$。

类似地，给定数列的前三项$a_1=1$，$a_2=8$，$a_2=27$，则$p(x)=x^3$和$p(x)=6x^2-11x+6$也都满足$p(1)=1$，$p(2)=8$，$p(3)=27$，下一项可以是$64$，也可以是$58$。

一般地，取数列的前k项$a_1,\ldots, a_k$，则我们可以根据“简单优先”的原则用一个不超过k-1次的多项式函数$p_k(x)$来拟合原数列，并记录$p_k(n)\neq a_n$的第一个自然数n。

例如在上例中，原数列为$a_n=n^3$，则 \begin{align*} &p_1(x)=1 && p_1(n)=1,\mathbf{\color{red}1}, 1, 1, \ldots\\ &p_2(x)=7x-6 && p_2(n)=1, 8, \mathbf{\color{red}15}, \ldots\\ &p_3(x)=6x^2-11x+6 && p_3(n)=1, 8, 27,\mathbf{\color{red}58}, \ldots\\ &p_4(x)=x^3 && p_4(n)=1, 8, 27, 64, 125, \ldots \end{align*} 由于$a_n$本身就由三次多项式生成，因此不难验证$k>=4$时，$p_k(n)$总是等于$a_n$。对其它k，首个满足$p_k(n)\neq a_n$的值$p_k(n)$已用红色标记，它们的和是$1 + 15 + 58 = 74$。

考虑由以下十次多项式所生成的数列： $$a_n = 1-n+n^2-n^3+n^4-n^5+n^6-n^7+n^8-n^9+n^{10}$$ 对每个k，找出首个满足$p_k(n)\neq a_n$的值$p_k(n)$，并求所有这些数的和。

本题难度:

解答

求出k从1取到10时的插值多项式，再找到第一个符合要求的n即可。

下面的代码使用了numpy的库（Python3版本），欲自行实现多项式插值的读者可以使用牛顿法，此处因涉及节点的增加，是典型的牛顿法优于拉格郎日法的情况。

结果是$37076114526$。

import numpy.polynomial.polynomial as np
import numpy

x=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
y=[(1+n**11)//(1+n) for n in x]

m=0
for i in range(1,11):
    c=np.polyfit(x[:i],y[:i],i-1)[::-1]
    j=i
    while int(numpy.polyval(c,x[j]))==y[j]:
        j+=1
    m=m+numpy.polyval(c,x[j])

print(round(m),int(m),m)