递推关系

Grade Open Time Friday, 19 September 2014, 10:07 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:07 am
Allow late Yes Close Time Friday, 26 September 2014, 10:07 am
Input file recurrences.in Output file 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.