记录编号	35449	评测结果	AAAAAAAAAA
题目名称	线性递推式	最终得分	100
用户昵称	Makazeu	是否通过	通过
代码语言	C++	运行时间	0.006 s
提交时间	2012-02-21 22:18:36	内存使用	0.27 MiB

#include <cstdio>
#include <cstdlib>
#include <iostream>
using namespace std;
const int MOD=9973;
const int MAXN=12;
class Matrix
{
public:
	int m[MAXN][MAXN];
};
Matrix A,B;

unsigned long long  N,K;
void init()
{
	scanf("%d",&N);
	cin>>K;
	for(int i=2;i<=N;i++) A.m[i][i-1]=1;
	int x;
	for(int i=1;i<=N+1;i++)
	{
		scanf("%d",&x);
		A.m[i][N]=x;
	}
	A.m[N+1][N+1]=1;
}

Matrix multiply(Matrix M,Matrix P)
{
	Matrix T;
	for(int i=1;i<=N+1;i++)
		for(int j=1;j<=N+1;j++)
				T.m[i][j]=0;
	for(int i=1;i<=N+1;i++)
		for(int j=1;j<=N+1;j++)
			for(int k=1;k<=N+1;k++)
				T.m[i][j]=(T.m[i][j]+M.m[i][k]*P.m[k][j])%MOD;
	return T;
}

Matrix pow(unsigned long long k)
{
	Matrix T;
	if(k==1) {return A;}
	T=pow(k/2);
	T=multiply(T,T);
	if(k%2==1) {T=multiply(T,A);}
	return T;
}

int main()
{
	freopen("recursion.in","r",stdin);
	freopen("recursion.out","w",stdout);
	init();
	B=pow(K);
	int Ans=B.m[N+1][1];
	int x;
	for(int i=1;i<=N;i++)
	{
		scanf("%d\n",&x);
		Ans=(Ans+B.m[i][1]*x)%MOD;
	}
	printf("%d\n",Ans%MOD);
	return 0;
}