「FJ2015集训」热身题

2015年7月12日2,7331

「问题描述」

定义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分

 

说点什么

提醒
avatar
Binary10
Binary10

这个封面图片也是醉了