poj 3233 Matrix Power Series (矩阵快速幂+分治)

题目链接

题意:

Given a n × n matrix A and a positive integer k, find the sum S = A + A2 + A3 + … + Ak.

思路: 对k进行二分。

比如,当k=6时,有:
A + A^2 + A^3 + A^4 + A^5 + A^6 =(A + A^2 + A^3) + A^3*(A + A^2 + A^3)
应用这个式子后,规模k减小了一半。我们二分求出A^3后再递归地计算A + A^2 + A^3,即可得到原问题的答案。

以及错误的递归方式:

screenshot-from-2016-10-19-16-12-57

无形中增加了多少次。。。。。。怎么像小学生呢。。。

screenshot-from-2016-10-19-16-12-57

正确的写法。。。

screenshot-from-2016-10-19-16-14-08

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz