题意
已知(f_m=sumlimits_{i=1}^k a_iv_i^m)，不过(a)已经忘掉了。幸运的是已经计算好了(f_{1...k})，想要的是(f_n)。给定(f_{1...k},v_{1...k})。对(1004535809)取模。
做法
我们猜测对于任意(n(n>k))，有(f_n=sumlimits_{i=1}^k c_if_{n-i})，也就是(k)阶线性递推
令(c_0=-1)，则(sumlimits_{i=0}^k c_if_{n-i}=0)
(sumlimits_{j=0}^k c_jsumlimits_{i=1}^k a_iv_i^{n-j}=0Longrightarrow sumlimits_{i=1}^k a_isumlimits_{j=0}^k c_jv_i^{n-j}=0)
我们想要(sumlimits_{j=0}^k c_jv_i^{n-j})恒等于(0)，只需(G(x)=c_0x^k+c_1x^{k-1}+cdots+c_{k-1}x^{1}+c_kx^{0})的零点为(v_{1...k})
显然(G(x)=l(x-v_1)(x-v_2)cdots(x-v_{k-1})(x-v_{k}))（(l)为常数），因为(c_0=-1)，所以(l=-1)，然后算出(G(x))后就能得出(c_{1...k})了