学步园

矩阵这个东西还是很好用的，这回开始深入学习。

参考了：http://www.cnblogs.com/jianglangcaijin/archive/2012/12/29/2838328.html

题目链接：http://acm.fzu.edu.cn/problem.php?pid=1683

题意：f(0)=1,f(1)=3,f(2)=5,f(n)=3f(n-1)+2f(n-2)+5f(n-3)。求s(n)=(f(0)+f(1)……+f(n))%2009。

思路：S(n)=S(n-1)+F(n)=S(n-1)+3F(n-1)+2F(n-2)+7F(n-3)，因此构造矩阵：

#include <cstdio>
#include <cstring>

const int N=5;
const int mod=2009;

class Matrix
{
public:
	int a[N][N];
	int n;   //矩阵大小

	void init (int x)
	{
		memset(a,0,sizeof(a));
		if (x) for (int i=0;i<N;i++)
			a[i][i]=1;
	}

	void read (int _n)
	{
		n=_n;      //
		for (int i=0;i<n;i++)
			for (int j=0;j<n;j++)
			{
				scanf("%d",&a[i][j]);
				a[i][j]%=mod;
			}
	}

	Matrix operator + (Matrix b)
	{
		Matrix c;
		for (int i=0;i<n;i++)
			for (int j=0;j<n;j++)
				c.a[i][j]=(a[i][j]+b.a[i][j])%mod;
		return c;
	}

    Matrix operator + (int x)
	{
		Matrix c=*this;
		for (int i=0;i<n;i++)
			c.a[i][i]+=x;
		return c;
	}

	Matrix operator * (Matrix b)
	{
		Matrix p;
		p.n=b.n;   //
		p.init(0);
		for (int i=0;i<n;i++) for (int j=0;j<n;j++)
			for (int k=0;k<n;k++)
				(p.a[i][j]+=a[i][k]*b.a[k][j]%mod)%=mod;
		return p;
	}

	Matrix power (int t)
	{
		Matrix ans,p=*this;
		ans.n=p.n;  //
		ans.init(1);
		while (t)
		{
			if (t&1) ans=ans*p;
			p=p*p;
			t>>=1;
		}
		return ans;
	}

	void print (int n)
	{
		for (int i=0;i<n;i++)
			for (int j=0;j<n;j++)
				printf(j==n?"d\n":"%d ",a[i][j]);
	}
}a;


int main ()
{
#ifdef ONLINE_JUDGE
#else
	freopen("read.txt","r",stdin);
#endif
	int T,n;
	scanf("%d",&T);
	for (int Cas=1;Cas<=T;Cas++)
	{
	    scanf("%d",&n);
        if (n<=2)
        {
            printf("Case %d: %d\n",Cas,(n+1)*(n+1));
            continue;
        }
        a.n=4;
        a.init(0);
        a.a[0][0]=1;a.a[0][1]=3;a.a[0][2]=2;a.a[0][3]=7;
        a.a[1][1]=3;a.a[1][2]=2;a.a[1][3]=7;
        a.a[2][1]=1;
        a.a[3][2]=1;
        a=a.power(n-2);
        int ans=(a.a[0][0]*9+a.a[0][1]*5+a.a[0][2]*3+a.a[0][3])%mod;
        printf("Case %d: %d\n",Cas,ans);
	}
	return 0;
}