[Algorithm]Fast Pow

快速幂运算，对于求解x^n，pow(x, n)的问题，如果我们采用最naive的方法，也就是一直乘，那么时间复杂度为O(n)，但是很多时候我们需要求特么大的n，那么O(n)的方法显然是十分不效率的，我们需要更快的方法。
首先我们可以想到，如果我们知道pow(x, n / 2)的值，我们只需要一次乘法就可以求得pow(x, n) = pow(x, n / 2) * pow(x, n / 2)。那么我们用divide and conquer的思路即可，对于规模为n的为题p，我们只需要将其reduce成n / 2规模的问题p'，根据p'问题的答案，我们可以在常数时间求得p问题的答案，T(n) = T(n / 2) + 1。从而T(n) = O(log n)，代码如下：


另外我们还有一种更普遍的基于二进制的方法，对于x^n中的n，用二进制表示的话可以表示为，n = a0 * 2^0 + a1 * 2^1 + a2 * 2 ^ 2 + ... + ak * 2^k，where ai in [0, 1]。那么x^n = x^(a0 * 2^0) * x^(a1 * 2^1) * ... * x^(ak * 2^k)，也就是说我们只需要求x^0, x^1, x^2...x^k的值。那么我们根据n的二进制表示就可以把x^n在O(log n)的时间当中求出来，代码如下：



类似的思想不仅仅可以用于乘法，比如对于Divide Two Integers这道题，我们用减法实现除法的过程中也用了类似的思想，具体讲解可以参考这篇文章。
当然Fast Pow的应用不只限于数字，对于任何可以重载乘法的数据类型都是适用的。比如矩阵，我们有的时候也会需要快速求一个矩阵的n次方，当然前提是矩阵的行列数目一样。例如POJ 3070，可以通过矩阵的n次方来求出斐波那契的第n项，如果我们用Fast Pow的思路，我们可以在O(log n)的时间完成这项工作。具体解法可以参考这篇文章。
矩阵在图当中也是很常见的，比如我们可以用邻接矩阵表示一个图。假设图(有向无向皆可，edge没有weight)有n个顶点，有邻接矩阵为m。m^k[u][v]就为从顶点u到顶点v经过k个顶点的路径的数量。m^1 + m^2 + m^3 + ... m^n - 1也可以用表示图的传递闭包。具体的讲解可以参考这篇文章。