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
v1a9r9u8n:
2018-10-15 10:58:20
Can't we use the idea of sum of geometric progression somehow? Last edit: 2018-10-15 11:31:31 |
|
ayush926:
2018-06-27 16:33:07
Matrix exponentiation. Learned a lot! |
|
hazard_10:
2018-05-13 04:08:00
I am getting TLE on using Matrix exponentiation any hints ?? |
|
galang:
2016-09-15 17:30:09
%I64d gives wa
|
|
Yash:
2015-02-17 12:24:35
Nice Question...Good exercise for Matrix Expo :) |
|
ISHANI:
2015-02-03 20:22:41
Simple as SEQ... |
|
Curiosa:
2013-07-01 06:42:46
This one sample test is as useless as 'g' in lasagna. @Author Please provide some other tests. |
|
Sandeep Singh Jakhar:
2013-01-01 06:38:45
Finally...got it Last edit: 2013-01-01 06:39:16 |
|
(Tjandra Satria Gunawan)(曾毅昆):
2012-12-30 10:32:11
It's very hard to get accepted with python code, My top speed C code "for now" AC in 0.05s, same algo with python 2 and python 3 but TLE (>7s)... |
|
[Rampage] Blue.Mary:
2012-11-21 04:51:42
After solving this, try http://www.spoj.pl/problems/SPP2/ |
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 |