本文从WordPress迁移而来, 查看全部WordPress迁移文章
hdu 3306 Another kind of Fibonacci
转化一下公式吧
构造一个矩阵 ( si-1,Ai^2 , Ai-1 ^ 2) , 得到 (si , Ai+1 ^ 2 , Ai^2)
Ai + 1 = X Ai + Y Ai - 1 , Ai + 1^2 = X^2 Ai^2 + Y^2 Ai^2 + 2 X Y Ai Ai - 1
多了 Ai * Ai-1 这个项,所以就往矩阵里面加点东西吧…
( si-1,Ai^2 , Ai-1 ^ 2 , Ai Ai-1) ——> (si , Ai+1 ^ 2 , Ai^2 , Ai+1 Ai)
看看Ai+1 Ai , Ai+1 Ai = (X Ai + Y Ai-1) Ai = X Ai^2 + Y Ai Ai-1
这样就有Ai*Ai-1了
1 | 构造矩阵 |
1 |
|
hdu 1588 Gauss Fibonacci
这题的话,挺好的,其实有之前两道矩阵题的结合
fibs矩阵(简称A)
1 | 1 1 |
它的幂次就是对应的fibs项
所以f(g(i))统一用fibs矩阵表示
1 | f(g0) = f(b) = A^b |
求和,那么首先把A^b提出来,剩下A^k + A^2k + A^3K …………………
把A^k单独看为B,变为B + B^2 + B^3 + B^4 + ……………….
这就变成了 poj 3233 Matrix Power Series 可以两种方法做
另外,考虑一下b = 0,k = 0的话,会怎样?
1 |
|