递推关系

成绩 开启时间 2014年09月19日 星期五 10:07
折扣 0.8 折扣时间 2014年09月26日 星期五 10:07
允许迟交 是 关闭时间 2014年09月26日 星期五 10:07
输入文件 recurrences.in 输出文件 recurrences.out

【题目描述】

考虑如下所示的递推关系：

f(n)=a1*f(n-1)+a2*f(n-2)+...+ad*f(n-d)，对n>d。

a1,a2,...,ad是任意常数。

一个著名的例子是Fibonacci数列：f(1)=1,f(2)=1,f(n)=f(n-1)+f(n-2)，在这里d=2,a1=1,a2=1.

每一个这样的递推关系都由d（即递推的阶数），a1,a2,...,ad的值，f(1),f(2),...,f(d)的值唯一确定。给你这些值，和两个正整数n,m。你的任务是计算f(n)模m的值。

【输入格式】

输入文件包含多组数据。

每组数据有3行：

第1行是3个正整数d,n,m。

第2行是d个非负整数a1,a2,...,ad。

第3行是d个整数f(1),f(2),...,f(d)。

两组数据之间由一个空行分隔。

【输出格式】

对每组数据，输出一行1个非负整数：f(n)模m的值。

【样例输入】

1 1 100

2

1


2 10 100

1 1

1 1


3 2147483647 12345

12345678 0 12345

1 2 3


0 0 0

【样例输出】

1

55

423

【提示】

数据组数<=150

对于100%的数据：

1<=d<=15

1<=n<=2^31-1

1<=m<=46340

所有的输入数据均在32位带符号整数范围内。

输入结束标志为d=n=m=0.

【来源】

UVa10870 Recurrences

刘汝佳，《算法竞赛入门经典训练指南》表2-12

Problem setter: Max Furlong

Special Thanks: Derek Kisman, EPS.