1493. [UVa 10870] 递推关系

【题目描述】

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

$f(n)=a_1f(n-1)+a_2f(n-2)+...+a_df(n-d)(n>d)$

$a_1,a_2,...,a_d\in Z$

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

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

【输入格式】

输入文件包含多组数据。

每组数据有3行：

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

第2行是d个非负整数$a_1,a_2,...,a_d$。

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

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

【输出格式】

对每组数据，输出一行1个非负整数：$f(n)\mod 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

【提示】

数据组数$\leq 150$

对于100%的数据：$1\leq d\leq 15,1\leq n\leq 2^{31}-1,1\leq m\leq 46340$

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

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

【来源】

UVa 10870 Recurrences

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

Problem setter: Max Furlong

Special Thanks: Derek Kisman, EPS.