SPP - Recursive Sequence (Version II)
Sequence (ai) of natural numbers is defined as follows:
ai = bi (for i <= k)
ai = c1ai-1 + c2ai-2 + ... +
ckai-k (for i > k)
where bj and cj are given natural numbers for 1<=j<=k. Your task is to compute am + am+1 + am+2 + ... + an for given m <= n and output it modulo a given positive integer p.
Input
On the first row there is the number C of test cases (equal to about 50).
Each test contains four lines:
k - number of elements of (c) and (b) (1 <= k <= 15)
b1, ... bk - k natural numbers where 0 <= bj <= 109 separated by spaces.
c1, ... ck - k natural numbers where 0 <= cj <= 109 separated by spaces.
m, n, p - natural numbers separated by spaces (1 <= m <= n <= 1018, 1<= p <= 108).
Output
Exactly C lines, one for each test case: (am + am+1 + am+2 + ... + an) modulo p.
Example
Input: 1 2 1 1 1 1 2 10 1000003 Output: 142
hide comments
twoam:
2024-05-14 21:15:16
An edge case is kind of annoying. B's should have had some ordering. |
|
kk108:
2021-11-24 19:52:06
why my code is giving wrong answer?
|
|
divyn:
2021-08-29 14:12:00
my solution is working fine on local machine, while submitting i am getting runtime error SIGKILL. Last edit: 2021-08-29 14:13:16 |
|
rgalpha:
2020-12-22 13:11:26
Ensure that the returned answer is positive. One way is to use ((b-a)%p+p)%p. |
|
shantanu_23:
2020-07-20 12:48:01
Try Modular Arithematic. The complexity should be K^3log(N) |
|
hetp111:
2019-12-22 10:21:00
Nice one...! Last edit: 2019-12-22 10:45:14 |
|
hvh2911:
2019-12-06 10:45:31
%I64d wrong answer ??
|
|
sk_23:
2019-06-18 09:19:53
Same as this problem ::==> https://www.spoj.com/problems/FIBOSUM/ |
|
sanjiv1970:
2019-01-27 15:39:39
yes yes yes yes!!!!!
|
|
ankitpriyarup:
2018-12-11 14:17:00
Finally AC :)
|
Added by: | Fudan University Problem Setters |
Date: | 2008-05-15 |
Time limit: | 3s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: C99 ERL JS-RHINO NODEJS PERL6 VB.NET |
Resource: | Problem SEQ |