「问题描述」

定义F：

F(1) = 1,

F(2) = 2,

F(n) = F(n-1) + F(n-2) (n >= 3)

定义p：

p(i) = a1*F(1)^i + a2*F(2)^i + … + ak*F(k)^i

其中k和a1…ak为常数。

现在已知k,p(1),p(2),…,p(k)，求p(k+1)。为了避免高精度，所有运算都模掉M。保证F(1),…,F(n)在模质数M下两两不同，保证有唯一解。

「输入格式」

第一行，两个整数k,M。

第二行，p(1), p(2), . . . , p(k) 模 M 。

「输出格式」

输出p(k+1)模M。

「样例输入1」

3 101

5 11 29

「样例输出1」

83

「样例输入2」

4 619

5 25 125 6

「样例输出2」

30

「数据规模与约定」

对于20%的数据，k<=10

对于50%的数据，k<=100

对于100%的数据，1<=k<=4000， 3<=M<=10^9

题解

50分是裸高斯消元

lazycal：

F1   F2   … Fk

F1^2 F2^2 … Fk^2

F1^3 F2^3 … Fk^3

F1^4 F2^4 … Fk^4

…

F1^k F2^k … Fk^k

可以发现系数是有规律的。我们可以用第i行减掉第i-1行*F1，这样就可以将第1列中除了第1行的数清零。同理第2列，第3列。。。这样就可以得到一个上三角矩阵。而且第i行第j列的数为Fj*(Fj-F1)*(Fj-F2)*…*(Fj-Fi-1)。然后就可以解出a1…ak。然后算出Fk+1，得到答案。

上述做法常数实现的好的话应该可以过。

但是这题毕竟不需要求出a1…ak，所以我们可以将第k+1个方程写在最下方，也参与消元。最终最后一个方程的系数都被消为0，此时等号右边的值即为答案。

50分

100分