记录编号	414923	评测结果	AAAAAAAAAA
题目名称	[UVa 10870] 递推关系	最终得分	100
用户昵称	yymxw	是否通过	通过
代码语言	C++	运行时间	0.197 s
提交时间	2017-06-15 11:44:57	内存使用	0.32 MiB

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
using namespace std;
inline long long read()
{
  long long x=0,f=1;
  char ch=getchar();
  while(ch<'0'||ch>'9')
  {
    if(ch=='-')
      f=-1;
    ch=getchar();
  }
  while(ch>='0'&&ch<='9')
  {
    x=(x<<1)+(x<<3)+ch-'0';
    ch=getchar();
  }
  return x*f;
}
long long d,n,m;
long long b[20],f[20];
struct ying
{
  long long a[20][20];
  ying()
  {
    memset(a,0,sizeof(a));
  }
};
ying mul(ying &aa,ying &b,int mod)
{
  ying c;
  for(int i=0;i<15;++i)
    for(int j=0;j<15;++j)
    {
      c.a[i][j]=0;
      for(int k=0;k<15;++k)
        c.a[i][j]+=(aa.a[i][k]*b.a[k][j]);
      c.a[i][j]%=mod;
    }
  return c;
}
ying init()
{
  ying res;
  for(int i=0;i<15;++i)
    for(int j=0;j<15;++j)
      res.a[i][j]=(i==j);
  return res;
}
ying ks(ying aa,int k,int mod)
{
  ying res=init();
  while(k)
  {
    if(k&1)
      res=mul(res,aa,mod);
    k>>=1;
    aa=mul(aa,aa,mod);
  }
  return res;
}
int haha()
{
  freopen("recurrences.in","r",stdin);
  freopen("recurrences.out","w",stdout);
  while(1)
  {
    d=read();n=read();m=read();
    ying A,B;
    if(d==0&&n==0&&m==0)
      break;
    for(int i=0;i<d;++i)
      b[i]=read();
    for(int i=0;i<d;++i)
      f[i]=read();
    for(int i=0;i<d;++i)
      A.a[0][i]=b[i];
    for(int i=1;i<d;++i)
      A.a[i][i-1]=1;
    for(int i=0;i<d;++i)
      B.a[d-i-1][0]=f[i];
    ying res=ks(A,n-d,m);
    res=mul(res,B,m);
    printf("%d\n",res.a[0][0]);
  }
  //system("pause");
  return 0;
}
int sb=haha();
int main()
{;}