3
Can someone help me with simplifying this sequence. I write code to loop through entire n, I am getting timeout.
Hack sequence of IndiaHacks-2014 if given as below Hi = 2014*Hi-1 + 69*Hi-2 for (i > 2); Hi = 1 for (i <= 2)
Given n, you need to find nth term of Hack sequence modulo (109 + 7), i.e Hn % (109 + 7).
This is a Code golf problem. You need to write code with minimum number of characters.
Input: First line contain T, the number of test cases. Each of next T lines contain an integer n.
Output: For each test case output a single integer which is Hn modulo (109 + 7).
Constraints : 1 ≤ T ≤ 103, 1 ≤ n ≤ 1015
Sujith
Posted 2014-04-03T10:05:21.553
Reputation: 39
I'm sure that this would make sense on the IndiaHacks website if I could be bothered to create an account in order to see it, but in copying it across you've lost whatever formatting it had and it no longer makes sense. – Peter Taylor – 2014-04-03T10:13:10.373
Although if I'm correctly guessing what the formatting should be, it's essentially a duplicate of Fibonacci sequence.
– Peter Taylor – 2014-04-03T10:38:03.680Can you please tell me how to format questions here – Sujith – 2014-04-03T10:39:38.870
1Click on the help button next to the editor. It explains it in lots of detail. – Peter Taylor – 2014-04-03T10:41:06.890
1For fibonacci, we loop n completely. We can solve this problem without looping completely. – Sujith – 2014-04-03T10:41:07.430
1Improved your formatting, but are you sure about the
% (109 + 7)part? Or should it be% 109 + 7? BTW to see how I formatted your question, you can go to the review history (by clicking the "edited x minutes ago") and choose "side-by-side markdown" – user12205 – 2014-04-03T10:50:28.1031sorry.. it should be 10^9 + 7 – Sujith – 2014-04-03T10:52:36.017
If you're getting a timeout, it's probably not code golf. – user2357112 supports Monica – 2014-04-03T10:59:47.127
2Which other values are missing superscripts? I'm now suspicious of the bounds on the input, and half-suspicious of the number
2014. – Peter Taylor – 2014-04-03T11:11:25.460Hi = 2014Hi-1 + 69Hi-2 for (i > 2); Hi = 1 for (i <= 2) (H1 =1 & H2 = 1) – Sujith – 2014-04-03T11:12:04.510
1As for "looping completely", this problem is the same as the Fibonacci problem but with different parameters. Exactly the same approaches (direct recurrence, dynamic programming, matrix exponentiation, Binet's formula) apply. – Peter Taylor – 2014-04-03T11:14:25.937
Think this can be done by matrix exponentiation – Sujith – 2014-04-03T11:54:32.307