记录编号	35229	评测结果	AAAAAAAAAA
题目名称	线性递推式	最终得分	100
用户昵称	kaaala	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2012-02-18 10:54:09	内存使用	0.30 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>

using namespace std;

int N,a[13][13],b[13][13],c[13][13],f[13],fn[13],p[10001];
long long K;

int main()
{
	freopen("recursion.in","r",stdin);
	freopen("recursion.out","w",stdout);
	scanf("%d%lld",&N,&K);
	for(int i=0;i<N-1;i++)
		a[i][i+1]=1;
	for(int i=0;i<=N;i++)
		scanf("%d",&a[N-1][i]);
	for(int i=0;i<N;i++)
		scanf("%d",&f[i]);
	a[N][N]=1;
	f[N]=1;
	K-=N-1;
	for(int i=0;i<=N;i++)
		b[i][i]=1;
	p[0]=0;
	do
	{
		p[0]++;
		p[p[0]]=K%2;
		K/=2;
	}while(K!=0);
	for(int i=p[0];i;i--)
	{
		memset(c,0,sizeof(c));
		for(int j=0;j<=N;j++)
			for(int k=0;k<=N;k++)
			{
				for(int l=0;l<=N;l++)
					c[j][k]+=b[j][l]*b[l][k];
				c[j][k]%=9973;
			}
		for(int j=0;j<=N;j++)
			for(int k=0;k<=N;k++)
				b[j][k]=c[j][k];
		memset(c,0,sizeof(c));
		if(p[i]==1)
		{
			for(int j=0;j<=N;j++)
				for(int k=0;k<=N;k++)
				{
					for(int l=0;l<=N;l++)
						c[j][k]+=b[j][l]*a[l][k];
					c[j][k]%=9973;
				}
			for(int j=0;j<=N;j++)
				for(int k=0;k<=N;k++)
					b[j][k]=c[j][k];
		}
	}
	for(int i=0;i<=N;i++)
		for(int j=0;j<=N;j++)
			fn[i]+=f[j]*b[i][j];
	printf("%d\n",fn[N-1]%9973);
	return 0;
}