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

 

codeforces 560 D. Equivalent Strings(分治)

问两个长度相同的字符串是否等价.

相等的条件是,两个字符串相等,或者两个偶数长度(因为要分成长度相同的两段,所以一定是偶数长度才可分)字符串平均分成两部分,每部分对应相等(不考虑顺序)

一开始有一点没想清楚.

如果字符串a分成相等长度的两部分a1,a2,字符串b分成相等的两部分b1,b2

我错误得以为,如果a1和a2等价&&b1和b2等价,那么a 和 b 就相等了(a和b一定等价,但不一定相等),于是只判断了 equal(a1,b2)&&equal(a2,b1)

wa了一次.

<