Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom2月前

04/19
21:39
Fib循环节 快速幂 矩阵乘法

[2017.04.18 省选模拟赛] 隔壁老王的简单数列

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

moreD的隔壁室友(人称隔壁老王的)liouzhou_101最近选了数论课,经过一段时间的卓有成效的学习,他非常自信,认为自己的数论水平已经可以吊打全国 99.99\%的学生了。O(* ̄▽ ̄*)ブ
某天 12 点他正准备起床的时候,突然想到了这么一个问题:给出一个 n ,求 Fib(2^n)
这里的 Fib 定义为 Fib(0)=0, Fib(1)=1 , 对于 n\ge2, Fib(n)=Fib(n-1)+Fib(n-2)
然而还有一周数论就要期末考了,他还要好好复习争取吊打全国 100\% 的学生,于是他决定把这个问题交给一个骨骼精奇的小朋友——也就是你——来解决。如果你能成功解决这个问题,就可以得到来自liouzhou_101的祝福哦~
无畏的勇者(吐槽这个称号你就输了)啊,赶快解决这个问题,将全国学生从liouzhou_101的手里拯救出来吧!

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

本题有多组数据。第一行一个整数 T ,表示数据组数。接下来 T 行每行一个整数N,含义如题目所示。

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

输出共T 行,每行一个整数为所求答案。
由于答案可能过大,请将答案 mod \ 1125899839733759后输出

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

2
2
31

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

3
343812777493853

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

对于 20\% 的数据,n\le20
对于 40\% 的数据,n\le10^3
对于 70\% 的数据,n\le10^7
对于 100\% 的数据,n\le10^{15}, T\le5

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

关于Fibonacci数列的循环节,zimpha dalao的blog:

http://zimpha.github.io/2015/09/11/pisano-period/

然后题目中 pmod 5 = 4 的质数,所以 p - 1 肯定是一个循环节,先求出 2 ^ n \% p - 1 然后矩乘快速幂求解就可以了

 

[2017.04.18 省选模拟赛] 隔壁老王的简单数列