HDU 6050 Funny Function 矩阵快速幂 矩阵变化

http://acm.hdu.edu.cn/showproblem.php?pid=6050

Funny Function

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Problem Description

Function $F_{x,y}$satisfies:

For given integers N and M,calculate $F_{m,1}$ modulo 1e9+7.
Input
There is one integer T in the first line.
The next T lines,each line includes two integers N and M .
1<=T<=10000,1<=N,M<2^63.
Output
For each given N and M,print the answer in a single line.

Sample Input

2
2 2
3 3

Sample Output

2
33

Source

题意

给定上图公式和$n,m$,求$F_{m,1}$

思路

可以发现,$F_{i,j} = F_{i,j-1}+2*F_{i,j-2}$,对于每行,维护出$F_j, F_{j-1},Sum_j,F_1$,用矩阵快速幂计算即可。转移到下一行,
$$F_j = Sum_{n+1} - F_1$$
$$F_{j-1} = Sum_{n+1} - F_n$$
$$Sum_j = 2* Sum_{n+1} -  F_1 - F_n$$
$$F_1 = Sum_{n+1} - F_n$$
上述变化是线性的,前面乘以一个矩阵即可表示。最后将所得的矩阵快速幂$m-1$次后,乘上维护的信息,就是最后的答案。

 

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注