BZPRO
#3231. [Sdoi2008]递归数列
内存限制：256 MiB
时间限制：1 Sec
提交
提交记录
讨论
题目描述
一个由自然数组成的数列按下式定义：
对于
i <= k
：
a
i
= b
i
对于
i > k: a
i
= c
1
a
i-1
+ c
2
a
i-2
+ ... + c
k
a
i-k
其中
b
j
和
c
j
（
1<=j<=k
）是给定的自然数。写一个程序，给定自然数
m
<=
n
,
计算
a
m
+
a
m+1
+
a
m+2
+ ... +
a
n
,
并输出它除以给定自然数
p
的余数的值。
输入格式
由四行组成。
第一行是一个自然数
k
。
第二行包含
k
个自然数
b
1
, b
2
,...,b
k
。
第三行包含
k
个自然数
c
1
, c
2
,...,c
k
。
第四行包含三个自然数
m
,
n
,
p
。
输出格式
仅包含一行：一个正整数，表示
(
a
m
+
a
m+1
+
a
m+2
+ ... +
a
n
) mod
p
的值。
样例
样例输入
2
1 1
1 1
2 10 1000003
样例输出
142
数据范围与提示
对于100%的测试数据：
1<= k<=15
1 <= m <= n <= 1018
BZPRO