范围:75分,1<=n<=1000000,1<=k,p<=1000000000.10分,1<=n<=1E18,1<=k,p<=1000.15分,1<=n<=1E18,1<=k<=1000000,1<=p<=1000000000.
题解:这题的范围告诉我们只要一项一项的推,线性算法可以过75分,考场上不多想拿了75分就过吧!再看后面10分.k和p较小,容易想到的就是找出循环节.如果找出模k的循环节,循环节内部递推,循环节外部矩阵倍增即可.我们知道循环节的长度<=k^2.这是因为相邻两项决定着后面的项,而相邻两项模k的余数只有k^2种.既然如此,我们先线性递推找出循环节,同时找出要-1的地方(注意,-1得到的0和不-1得到的0要区别对待).这是O(k^2)的时间.具体说,找到循环节长度len后,x y z t是一般的斐波那契数列的递推矩阵的len次幂,考虑到题中定义,某几项模k余1,要减1,而这些减1累加到循环节末尾使末尾两项分别减去了delta1和delta2.这10分做法如下:找到循环节,总结矩阵;开头不循环处单独处理;中间有循环节处倍增之;末尾不循环处单独处理.这样时间为O(k^2+logn). 最后15分.还是k较小.这验证了我们的思路.总结矩阵后倍增已经没有优化余地了(O(logn)的时间),要考虑的是在优于k^2的时间内找出循环节,总结矩阵.我们发现,或者说显然地,在第一项模k余1之前这个数列和普通的斐波那契数列一样.模k余1之后,这一项减1,变成模k余0,也就是这个数列是….a 0 a a….我们如果把相邻两个0(注意是1减1得0的0,不是本来就是0的0!)之间的部分成为一段,那么共有k种段(因为段中数值完全取决于段首).也就是说,循环节中至多有k种不同的段.我们如果能快速地求出每段的长度,本题就几乎解决了.怎样求出段的长度呢?首先我们知道,段首是s并且s*t=1(mod k)的情况下,斐波那契数列中第一个=t(mod k)的数就是我们要找的位置.如果不存在s关于k的逆元t,或者斐波那契数列中根本没有=t(mod k)的项,这时可知后面完完全全是普普通通的斐波那契数列了,否则我们还是要找循环节.斐波那契数列中第一个mod k余t的数可能出现在哪里呢?粗略的估计肯定在前k^2项中,但是这样无法解决本题.编程验证之,可发现一定出现在前3k项中(怎么证?不知道).这样不错,我们可以扫描斐波那契数列的前3k项,找出每个s的逆元t在数列中最早出现的位置.15分做法:跳跃地球出循环节,总结矩阵;以下和前10分做法一样.
这题的数据范围怎么搞啊，
我定义变量范围可弱了，呃呃呃
亲，能不能告诉我定义变量有什么可注意的，还有怎么根据题中给的范围算出来自己算法的最大限制，若是把所有的变量都定义成longint有什么严重后果，本人自己noip曾经笔算过一道题，对拍了一下，结果就是计算失误，拍没了一等奖，留下严重阴影，求教lz及各大牛，指点一下悲催的我吧，相信有了你们我不会再悲催了