[Home|Training|Problems|Contests|C Language] | [Login|Register] |

Problems Status Rank |
Problem 1141
Recurrent sequence
Time Limit: 1000ms
Memory Limit: 65536kb Description
An array which only consists of natural numbers could be defined as below :
(1) for any i <= k , ai = bi ; (2) for any i > k , ai = c1*ai-1+c2*ai-2+...+ck*ai-k ; Note: bj and cj( 1<=j<=k) are natural numbers which have already been given. Given m and n( m <= n ) , please write a program to compute the result of am+am+1..+an , which is denoted by r , and the output should be the value of r mod p (p is a given natural number ) . Input
The input consists of several datasets( between 1 to 100,000 ). Every data set consists of 4 lines :
the first line is a natural number k ; the second line contains k natural numbers: b1 , b2 , ...,bk ; the third line contains k natural numbers : c1 , c2 , ...,ck ; the forth line contains 3 natural numbers : m , n , p . 1<=k<=15, 1<=m<=n<=10 ^{18}
0<=b_{1},b_{2},...b_{k},c_{1},c_{2},...,c_{k}<=10^{9}, 1<=p<=10^{8}
Output
The answer to every data set in the input file should take up one line . There should be one positive integer representing the value of ( am+am+1..+an ) mod p .
Sample Input
2 1 1 1 1 2 10 1000003 1 1 2 1 3 1000003 Sample Output
142 7 |

University of Science and Technology of China

Online Judge for ACM/ICPC

Processed in 1.4ms with 1 query(s).

Online Judge for ACM/ICPC

Processed in 1.4ms with 1 query(s).