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

#include <fstream>
#include <memory.h>
using namespace std;
ifstream fin("recursion.in");
ofstream fout("recursion.out");
long long a[100],f[100],Template[12][12],Matrix[12][12],N,K;
long long Vector[12],Ans[12];
void Initialize()
{
long long i,j;
	fin>>N>>K;
	for(i=0;i<=N;i++)
		fin>>a[i];
	for(i=1;i<=N;i++)
		fin>>f[i],Vector[i]=f[i];
	for(i=1;i<=N;i++)
		Template[i][N]=a[i-1];
	N++;
	for(i=2;i<=N;i++)
		Template[i][i-1]=1;
	Template[N][N]=1;
	f[N]=a[N-1];Vector[N]=a[N-1];
	for(i=1;i<=N;i++)
		for(j=1;j<=N;j++)
			Matrix[i][j]=Template[i][j];
	Template[N][N]=1;
}

void Timed_Matrix(long long x)
{
long long i,j,k,tmp[12][12];
	if(x==1)
		return;
	else
		Timed_Matrix(x/2);
	memset(tmp,0,sizeof(tmp));
	for(i=1;i<=N;i++)
		for(j=1;j<=N;j++)
			for(k=1;k<=N;k++)
			{
				tmp[i][j]+=Matrix[i][k]*Matrix[k][j];
				tmp[i][j]%=9973;
			}
	memset(Matrix,0,sizeof(Matrix)); 
	if(x%2!=0)
		for(i=1;i<=N;i++)
			for(j=1;j<=N;j++)
				for(k=1;k<=N;k++)
				{
					Matrix[i][j]+=tmp[i][k]*Template[k][j];
					Matrix[i][j]%=9973;
				}
	else
		for(i=1;i<=N;i++)
			for(j=1;j<=N;j++)
				Matrix[i][j]=tmp[i][j];
}

int main()
{
long long i,j;
	Initialize();
	
	Timed_Matrix(K);
long long tmp[12];
	memset(tmp,0,sizeof(tmp));
	for(i=1;i<=N;i++)
		for(j=1;j<=N;j++)
		{
			tmp[i]+=Matrix[j][i]*f[j];
			tmp[i]%=9973;
		}
	fout<<tmp[1]<<endl;
	fin.close();
	fout.close();
	return 0;
}