Google code jam 2008 R1A – Numbers矩阵实现-码农场

题目链接在https://code.google.com/codejam/contest/32016/dashboard#s=p2 ，初看此题，第一反应是绝对不会是用浮点数求n次方。随后观察底数，觉得很像高中二项式定理。根据共轭复数（正数）的n次方之和等于一个整数X_n的原理，问题转化为求解X_n。设两个共轭复数的n次方分别为A_n，B_n，则有X_n=A_n+B_n，设两个系数求解可以发现X_n=6X_n-1-4X_n-2，有了这个公式，就可以用迭代的思想初步做出解答：

#include <iostream>
#include <iomanip>
using namespace std;
///////////////////////////SubMain//////////////////////////////////

short calculateX(const int &n)
{
	if (n == 0)
	{
		return 2;
	}
	else if (n == 1)
	{
		return 6;
	}
	else
	{
		return (10000 + 6 * calculateX(n - 1) - 4 * calculateX(n - 2)) % 1000;
	}
}

int main(int argc, char *argv[])
{
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	int nCases = 0;
	cin >> nCases;
	cin.get();
	for (int i = 0; i < nCases; i++)
	{
		int n = 0;
		cin >> n;
		cout << "Case #" << i + 1 << ": ";
		cout << setfill('0') << setw(3) << calculateX(n) - 1 << endl;
	}
	fclose(stdin);
	fclose(stdout);

	return 0;
}
///////////////////////////End Sub//////////////////////////////////

老实说，写完之后自我感觉良好，厚着脸皮自我感觉代码简洁优雅，每次迭代结果不大于999不会溢出，应该没问题了。但是在跑small的时候就堆栈溢出了，将linker堆栈参数调到最大，依然是StackOverflow。打开任务管理器，好家伙，一个控制台程序吃了一个G的内存，而且程序迭代奇慢无比，瞬间感觉脸红羞愧。

于是思考着将Xn+mXn-1化作等比数列，可惜系数是无理数，如果用浮点数计算后面会产生非常大的误差。这时觉得仅凭高中数学知识没法解决。只好厚着脸皮搜索前人的解法，看到这篇文章http://www.cppblog.com/baby-fly/archive/2009/08/28/94622.html 才茅塞顿开。等比数列解决不了的，就用矩阵吧。我在这篇文章的基础上进行了改进，全部使用2 * 2的矩阵，写出最终的代码：

#include <iostream>
#include <iomanip>
using namespace std;
///////////////////////////SubMain//////////////////////////////////

class CMatrix
{
public:
	int m[4];
	CMatrix(int x1 = 6, int x2 = -4, int x3 = 1, int x4 = 0)
	{
		m[0] = x1;
		m[1] = x2;
		m[2] = x3;
		m[3] = x4;
	}

	CMatrix operator*(const CMatrix & other)
	{
		CMatrix r;
		r.m[0] = (m[0] * other.m[0] + m[1] * other.m[2] + 1000 * 1000) % 1000;
		r.m[1] = (m[0] * other.m[1] + m[1] * other.m[3] + 1000 * 1000) % 1000;
		r.m[2] = (m[2] * other.m[0] + m[3] * other.m[2] + 1000 * 1000) % 1000;
		r.m[3] = (m[2] * other.m[1] + m[3] * other.m[3] + 1000 * 1000) % 1000;
		return r;
	}

	CMatrix power(int n)
	{
		if (n == 1)
		{
			return *this;
		}
		CMatrix temp = this->power(n / 2);
		if (n % 2 == 0)
		{
			
			return temp * temp;
		}
		else
		{
			return temp * temp * *this;
		}
	}
};

int solve(int n)
{
	CMatrix m;
	m = m.power(n - 1) * CMatrix(6, 0, 2, 0);
	return m.m[0] - 1;
}

int main(int argc, char *argv[])
{
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	int nCases = 0;
	cin >> nCases;
	cin.get();
	for (int i = 0; i < nCases; i++)
	{
		int n = 0;
		cin >> n;
		cout << "Case #" << i + 1 << ": ";
		cout << setfill('0') << setw(3) << solve(n) % 1000 << endl;
	}
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

google code jam