hdu 4291 A Short problem (矩阵快速幂+广义斐波那契循环节||暴力找循环节)

题目链接

题意:

Given n (1 <= n <= 1018), You should solve for

g(g(g(n))) mod 109 + 7

where

g(n) = 3g(n – 1) + g(n – 2)
 

g(1) = 1
 

g(0) = 0
思路:找循环节。首先由于模数固定,可以暴力一下找到循环节。

得到1E9+7的循环节是222222224,222222224的循环节是183120.

然后三次矩阵快速幂就行了。

需要注意每次都要判断那一层的n是否为0和1。

暴力解法:

再来一个比较一般的做法:

参考递推式循环节

Acdreamer的博客_广义Fibonacci数列找循环节

摘重点:

今天早上起来后,看了下代码,为什么要判断5是不是p的模二次剩余呢,为什么是5呢

想了想,5对于斐波那契数列来讲,不就是x^2=x+1的delta么,那么这题的递推式是x^2=3*x+1,delta=3*3+4=13,然后我就把勒让德符号判断二次剩余那里改成13,然后对应的暴力出13及13以内的素数对应的循环节,交了一发,AC了

 

 

      所以综上所述:

是模的二次剩余时,枚举的因子

是模的二次非剩余时,枚举的因子

对于第二种非剩余的情况,理论上是枚举(p+1)(p-1)的因子,实际上常常只是枚举2*(p+1)的因子

对于c=5的情况,是有定理:

screenshot-from-2016-10-31-21-23-45

不过对于c不等于5的情况。。。该结论是否一定成立呢…感觉不是很好证,求指教。

 

说点什么

您将是第一位评论人!

提醒
wpDiscuz