记录编号	35283	评测结果	AAAAAAAAAA
题目名称	线性递推式	最终得分	100
用户昵称	Czb。	是否通过	通过
代码语言	C++	运行时间	0.013 s
提交时间	2012-02-19 20:52:15	内存使用	0.26 MiB

#include<stdio.h>

long long n,m,ans,a[12][12],tmp[12][12],h[100],t[100],f[12],g[12],top;

int main()
{
	freopen("recursion.in","r",stdin);
	freopen("recursion.out","w",stdout);
	long long i,j,k,x;
	scanf("%lld%lld",&n,&m);
	m=m-n+1;
	for(i=1;i<=n;i++)
	{
		a[i+1][i]=1;
	}
	for(i=1;i<=n;i++)
	{
		scanf("%lld",&a[i][n]);
	}
	a[n+1][n+1]=1;
	scanf("%lld",&ans);
	f[n+1]=ans;
	for(i=1;i<=n;i++)
	{
		scanf("%lld",&f[i]);
	}
	h[0]=1;
	for(i=1;i<=60;i++)
	{
		h[i]=h[i-1]*2;
	}
	for(i=60;i>=0;i--)
	{
		if(m>=h[i])
		{
			top++;
			t[top]=i;
			m-=h[i];
		}
	}
	for(x=0;x<=60;x++)
	{
		if(t[top]==x)
		{
			for(i=1;i<=n+1;i++)
			{
				g[i]=f[i];
				f[i]=0;
			}
			for(i=1;i<=n+1;i++)
			{
				for(j=1;j<=n+1;j++)
				{
					f[i]=(f[i]+g[j]*a[j][i])%9973;
				}
			}
			top--;
		}
		for(i=1;i<=n+1;i++)
		{
			for(j=1;j<=n+1;j++)
			{
				tmp[i][j]=a[i][j];
				a[i][j]=0;
			}
		}
		for(i=1;i<=n+1;i++)
		{
			for(j=1;j<=n+1;j++)
			{
				for(k=1;k<=n+1;k++)
				{
					a[i][j]=(a[i][j]+tmp[i][k]*tmp[k][j])%9973;
				}
			}
		}
	}
	printf("%lld\n",f[n]%9973);
	return 0;
}