hdoj4565 So Easy!

矩阵题,2013长沙邀请赛的题,但是貌似oj没有题目重现的比赛,没做到,结果长沙online居然出现了一道同一类型的题,,直接哭瞎了。。
需要用到无理数共轭的概念
具体题解:http://blog.csdn.net/xh_reventon/article/details/9970259
想到共轭就比较好做了。

hdoj4686 ——多校第9场A题

还是比较简单的题
思路;看到n的范围10^18,第一反应lg级别算法,然后发现时递推式,瞬间想到矩阵,既然是矩阵,自然是要推出aibi,然后很自然的会去想aibi有哪些组成部分推出来的呢,于是就会去把a和b的递推式左右分别乘乘一下。但是求的是所有aibi的和,简单,矩阵加一阶用来存储后面的aibi加起来的和即可。

poj3233

题意:计算A+A^2+A^3+…………+A^k.(其中A是一个矩阵,k很大)
首先,计算A的次方时用快速幂。又因为k很大,所以最后计算幂的加法时也要二分。
A+A^2+A^3…………+A^(2k+1)=A+A^2+…………+A^k+A^(k+1)+A^(k+1)*(A+A^2+…………+A^k)
A+A^2+A^3…………+A^2k=A+A^2+…………+A^k+A^k*(A+A^2+…………+A^k)
可见,要计算A+A^2+A^3+…………+A^k,只需计算A+A^2+…………+A^k和A^(k+1),或者A+A^2+…………+A^k和A^k。而计算A+A^2+…………+A^k的方式和原问题一致,如此递归,时间复杂度为log(k)(这个k是题意中的k)