[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)，代码如下：

	class Solution {
	public:
	double myPow(double x, int n) {
	if(!n)return 1;
	if(n == 1)return x;
	long pow = n;
	pow = abs(pow);
	double half = myPow(x, pow / 2), res = half * half;
	if(pow % 2)res *= x;
	return n < 0? 1 / res: res;
	}
	};

view raw Pow(x, n).cpp hosted with ❤ by GitHub

另外我们还有一种更普遍的基于二进制的方法，对于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)的时间当中求出来，代码如下：

	class Solution {
	public:
	double myPow(double x, int n) {
	if(!x)return x;
	if(!n)return 1;
	long pow = n;
	pow = abs(pow);
	if(n < 0)x = 1 / x;
	double res = 1;
	//n = k0 * 2^0 + k1 * 2^1 + ... + ki * 2^i (kj == 0/1)
	//res = x^(k0 * 2^0) * x^(k1 * 2^1) * ... * x^(ki * 2^i)
	while(pow)
	{
	if(pow & 1)res *= x;
	x *= x;
	pow >>= 1;
	}
	return res;
	}
	};

view raw Pow(x, n)_2.cpp hosted with ❤ by GitHub

类似的思想不仅仅可以用于乘法，比如对于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也可以用表示图的传递闭包。具体的讲解可以参考这篇文章。