# 矩阵加速线性递推式（转载）

Posted by 111qqz on Monday, October 17, 2016

## 快速求解多项递推式

＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊

＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊

| B A |                     | a1 |

N = M * M(1) =   |    a1           |

| Aa1+Ba0 |

|    an     |

N = M * M(n) =     |    an              |

| Aan+Ba(n-1)|

M^(n-1)*M1 =      |   F(n-1) |

|    F(n)   |

＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊

| 0    0 1 |                       | a1 |

| C   B A |                      | a2 |

M^(n-1)*M1 =         |   F(n-1) |

|    F(n)    |

|    F(n+1) |

＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊

M　阵的建立：若一共有 m　个递推式，则建一个m行m列的矩阵，让第m行从右到左依次是递推项的系数A,B,C…..，在除第一列和最后一行的剩余矩阵的主对角线上写1,其余所有的都写0.

M(1)   阵的建立：该矩阵是 m 行一列阵，其值分别为F(0),F(1)…F(m-1)

＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊

＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊

1.将n转化为二进制　n = bjb(j-1)…b2b1b0 bi = 0或1

2.M^2 = M*M   M^4 = (M^2)^2

3.M^n = (bjMj)(b(j-1)M(j-1))(b2M2)(b1M1)(b0M0)

M^9 = M^(1000+0+0+1) = M^1000*M^1

= M3*M0

4.模运算有这样的性质: (ab)%c = [(a%c)(b%c)]%c

＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊

SOJ:   cs.scu.edu.cn/soj

2984 Fibonacci

2385 Fibonacci Problem Again

2129 Sequence

1826 Number Sequence

3083 windy's cake III(只用到了二进制扫描法)

阿宽补充:tyvj p1947 p1155