【FJ2015集训】热身题

2015年7月12日2,3561

【问题描述】

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

 

  • Binary102015年10月19日 下午4:24 回复

    这个封面图片也是醉了

    #1