HDU2842 Chinese Rings 矩阵的应用

/*
取下前n个环步骤是先取下前n-2个环，再取下第n个环，再还原前n-2个环，最后取下前n-1个环。
递推公式：f(n) = f(n-1) + 2 * f(n-2) + 1
构造矩阵：
Fn(1,3) = |f(n) f(n-1) 1|
F2(1,3) = |f(2) f(1) 1| = |2 1 1|
         |1 1 0|
A(3,3) = |2 0 0|
         |1 0 1|
Fn = F2 * A^(n-2)
*/
#include "Mat.h"
#include <iostream>
using namespace std;

int a[3][3] = {1,1,0,2,0,0,1,0,1};
int main()
{
	Mat A(3,3),F(1,3);
	int s, i, j;
	mod = 200907;
	while(cin>>s && s)
	{
		if(s < 3)
		{
			cout<<s<<endl;
			continue;
		}
		A.clear();
		F.clear(2);F.s[0][0] = 2;
		for(i = 0; i < 3; i ++)
		{
			for(j = 0; j < 3; j++)
				A.s[i][j] = a[i][j];
		}
		A.Er_work(s-2);
		F.Multiply(A);
		cout<<(int)F.s[0][0]<<endl;
	}
	return 0;
}