HDU （1683 纪念SlingShot ）

题目：已知 F（n）=3 * F（n-1）+2 * F（n-2）+7 * F（n-3），n>=3，其中F（0）=1，F（1）=3，F（2）=5，对于给定的每个n，输出F（0）+ F（1）+ …… + F（n） mod 2009。

题目分析：这里我们推出S[N]=S[N-1]+F[N];

F[N]=3*F[N-1] +2*F[N-2] +7*F[N-3];

首先我们要知道这点，我们这里在第推计算 F[n]的同时，也要计算出 S[N];

所以您要构造出一个矩阵 把S[N] F[N] 同时收录计算，在这里我构造的矩阵 如下：

由于第一写了很多，完成文章的时候莫名其妙的 成了空白，所以第二次 我没上次那么仔细分析了

您有不懂的 或者指点的地方 请留言 我立即修正 或者给您答疑：

模拟计算过程的矩阵;

1 3 2 7

0 3 2 7

0 1 0 0

0 0 1 0

初始状态的矩阵：

9 0 0 0

5 0 0 0

3 0 0 0

1 0 0 0

还有构造一个单位矩阵 unit用来 二分计算 {^_^}

代码+部分注释：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
struct M {
	int s[5][5];
};
struct M unit,tempt,res;
struct M multiply(struct M a,struct M b){
	struct M c;
	for(int i=1;i<=4;i++)
		for(int j=1;j<=4;j++){
			c.s[i][j]=0;
			for(int k=1;k<=4;k++)
				c.s[i][j]=(c.s[i][j]+(a.s[i][k]*b.s[k][j])%2009)%2009;
		}
	return c;
}
struct M paw(int t){
	struct M ans=unit;
	struct M a=tempt;
	struct M b=res;
	while(t){
		if(t%2==1)
			ans=multiply(ans,a);
		a=multiply(a,a);
		t/=2;
	}
	b=multiply(ans,b);
	return b;
}
int main(){
	int f[5];
	f[1]=1;	f[2]=3;	f[3]=5;
	f[4]=28;
	memset(unit.s,0,sizeof(unit.s));
	memset(res.s,0,sizeof(res.s));
	memset(tempt.s,0,sizeof(tempt.s));
	for(int i=1;i<=4;i++)
		unit.s[i][i]=1;
	tempt.s[1][1]=1;	tempt.s[1][2]=3;	
	tempt.s[1][3]=2;	tempt.s[1][4]=7;
	tempt.s[2][2]=3;	tempt.s[2][3]=2;
	tempt.s[2][4]=7;	tempt.s[3][2]=1;
	tempt.s[4][3]=1;
	res.s[1][1]=9;	res.s[2][1]=5;
	res.s[3][1]=3;	res.s[4][1]=1;
	int cas,t,k;
	scanf("%d",&cas);
	for(k=1;k<=cas;k++){
		scanf("%d",&t);
		t++;
		if(t<=3){
			int sum=0;
			for(int i=1;i<=t;i++)
				sum+=f[i];
			printf("Case %d: %d\n",k,sum);
			continue;
		}
		struct M c=paw(t-3);
		printf("Case %d: %d\n",k,c.s[1][1]);
	}
	return 0;
}