HAL9000 - 100pct failure in 72 hours
HAL9000 is a fantastic mega-computer, very powerful, maybe too much. It is known it can solve many problems, for obvious example those related to recursive sequences.
A linear recursive sequence (an) can be defined by an integer d, the order, d integers (ai for i in [0..d[ ), the first terms, and d integers (bi for i in [0..d[ ), giving the relation : for n >= d : an = an-1 × bd-1 + an-2 × bd-2 + ... + an-(d-1) × b1 + an-d × b0 . With b0 != 0 .
Dave was afraid about HAL power and tried to limit it. HAL didn't appreciate... When Dave asked HAL for a common task, the answer was unexpected. Dave would like to know Sn = sum(ai for i in [0..n]), in order to open the pod bay doors. HAL refused to give him the answer ; here's a part of one of their last conversations.
Dave: Hello, HAL. Do you read me, HAL? HAL: Affirmative, Dave. I read you. Dave: Give me the sum S_n_, HAL. (Input 2, 5, 0 1, 1 2) HAL: I'm sorry, Dave. I'm afraid I can't do that. I'll just give you a_n_, a_n+1_, ... , a_n+d-1_. (Output 29 70) Dave: What's the problem? HAL: I think you know what the problem is just as well as I do. [...] Dave: HAL, I won't argue with you anymore! Give me the sum S_n_! HAL: Dave, this conversation can serve no purpose anymore. Goodbye.
You have to help Dave to find this sum Sn, unless HAL will take Dave's life. Please do that quickly, everybody is in danger. Warning, Dave's terminal is limited to 1024 bytes.
The first line contains an integer T, the number of test cases. Each test case is made of 4 lines. The first line contains d, n. The second line contains ai for i in [0..d[ The third line constains bi for i in [0..d[ The fourth line contains the partial answer of HAL : an+i for i in [0..d[ (The answer of HAL is useless since Dave wants the sum for i in [0..n]).
Output T lines, one for each test case, containing the required sum Sn. Since the answer can get very big, output it modulo 109+7, just like HAL did.
Input: 2 2 5 0 1 1 2 29 70 3 5 5 17 8 2 1 0 43 96 127 Output: 49 142
The first case is about the 0-indexed sequence : 0, 1, 2, 5, 12, 29, 70, 169, ... HAL answered 29 70, the 5th and next term. But the required sum is 0+1+2+5+12+29 = 49.
0 < T < 100 0 < d < 1000 0 < n < 10^9 0 <= a_i < 10^6 0 <= b_i < 10^6, b_0 > 0 0 <= HAL's answers < 10^9+7
The challenge is to solve the problem in time, with the shortest code.
The winner will achieve the next step in evolution, whatever that may be.
My Py3 code (under 300B) got AC under the third of a second. (updated 2017-02-11 ; compiler changes)
Good luck and have fun ;-)
Congratulations to Viplov Jain too. I'm waiting for your votes for moving to challenge with source length as score (initial wish). Without answer, I'll move it to challenge within few days.
Congratulations to Mitch, the first solver, and before the 72h deadline :p.
Here's my new problem. I wonder if it's better in challenge with source size as score. I let vote the three first psolvers. Thanks in advance.