记录编号	538107	评测结果	AAAAAAAAAA
题目名称	[UVa 10870] 递推关系	最终得分	100
用户昵称	Hale	是否通过	通过
代码语言	C++	运行时间	0.595 s
提交时间	2019-07-21 23:07:23	内存使用	13.66 MiB

#include<bits/stdc++.h>
#define LL long long
using namespace std;
int D,m,n,P;
struct matrix
{
	LL a[16][16];
	matrix operator * (const matrix &x) const
	{
		matrix res;
		for (int i=1;i<=D;i++)
		 for (int j=1;j<=D;j++)
		{
			res.a[i][j]=0;
			for (int k=1;k<=D;k++) res.a[i][j]=(res.a[i][j]+a[i][k]*x.a[k][j]%P)%P;
		}
		return res;
	}
	void clear()
	{
		for (int i=1;i<=D;i++)
		 for (int j=1;j<=D;j++) a[i][j]=0;
	}
} base,ans;
void pown(matrix x,LL k)
{
	while (k)
	{
		if (k&1) ans=ans*x;
		x=x*x;k>>=1;
	}
}
int main()
{
	freopen("recurrences.in","r",stdin);
	freopen("recurrences.out","w",stdout);
	while (scanf("%d%d%d",&D,&n,&m))
	{
		if (D==0&&n==0&&m==0) break;
		P=m;base.clear();
		for (int i=1;i<=D;i++)  
		{
			int x;scanf("%d",&x);
			base.a[i][1]=x;base.a[i][i+1]=1;
		}
		for (int i=1;i<=D;i++) 
		{
			int x;scanf("%d",&x);
			ans.a[1][D-i+1]=x;
		}
		if (n<=D) {printf("%d\n",ans.a[1][D-n+1]);continue;}
		pown(base,n-D);
		printf("%d\n",ans.a[1][1]);
	}
	return 0;
}