HDU 3936 FIB Query

  • 2018-08-07
  • 16
  • 0

题目:

We all know the definition of Fibonacci series: fib[i]=fib[i-1]+fib[i-2],fib[1]=1,fib[2]=1.And we define another series P associated with the Fibonacci series: P[i]=fib[4*i-1].Now we will give several queries about P:give two integers L,R, and calculate ∑P[i](L <= i <= R).

Input:

There is only one test case.
The first line contains single integer Q – the number of queries. (Q<=10^4)
Each line next will contain two integer L, R. (1<=L<=R<=10^12)

Output:

For each query output one line.
Due to the final answer would be so large, please output the answer mod 1000000007.

Sample Input:

2
1 300
2 400

Sample Output:

838985007
352105429

题目链接

p[1]+p[2]+…+p[n]

=f[1]^{2}+f[2]^{2}+…+f[2\times n-1]^{2}+f[2\times n]^{2}

=f[2\times n]\times f[2\times n+1]

利用此公式求得P,由于数据范围很大,斐波那契数列需要用矩阵快速幂递推求得。

\left[\begin{matrix}f(n)\f(n-1)\end{matrix}\right]=\left[\begin{matrix}1&1\1&0\end{matrix}\right]\times\left[\begin{matrix}f(n-1)\f(n-2)\end{matrix}\right] \tag{矩阵快速幂求斐波那契数列递推式}

AC代码:

评论

还没有任何评论,你来说两句吧