记录编号	433985	评测结果	AAAAAAAAAA
题目名称	[UVa 10870] 递推关系	最终得分	100
用户昵称	Hzoi_QTY	是否通过	通过
代码语言	C++	运行时间	0.434 s
提交时间	2017-08-06 20:01:48	内存使用	0.32 MiB

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iostream>
#define ll long long
using namespace std;
ll d,n,m;
struct qty
{
	ll f[16][16];
	qty()
	{
		memset(f,0,sizeof(f));
	}
}a,b;
inline qty operator *(qty a,qty b)
{
	qty c;
	for(int i=0;i<d;i++)
	   for(int j=0;j<d;j++)
	      for(int k=0;k<d;k++)
	         c.f[i][j]=(c.f[i][j]+(a.f[i][k]*b.f[k][j])%m)%m;
	return c;
}
int main()
{
	freopen("recurrences.in","r",stdin);
    freopen("recurrences.out","w",stdout);
	while(scanf("%lld%lld%lld",&d,&n,&m)==3)
	{
		if(n==0&&d==0&&m==0)break;
		a=qty();b=qty();
		for(int i=0;i<d;i++)
		   scanf("%lld",&b.f[0][i]);
		for(int i=1;i<d;i++)
		   b.f[i][i-1]=1;
		for(int i=0;i<d;i++)
		   scanf("%lld",&a.f[d-i-1][0]);
		qty ans;
		for(int i=0;i<d;i++)ans.f[i][i]=1;
		if(n<=d)
		{
			printf("%lld\n",a.f[0][d-n]%m);
			continue;
		}
		n-=d;
		while(n)
		{
			if(n&1)ans=ans*b;
			b=b*b;
			n/=2;
		}
		ans=ans*a;
		printf("%lld\n",ans.f[0][0]);
	}
}