TETRAHRD - Sum of Tetranacci numbers
The sequence of Tetranacci numbers is defined as follows:
an = an-1 + an-2 + an-3 + an-4 with a0 = a1 = a2 = 0 and a3 = 1.
Input starts with a positive integer t ≤ 4000, then t lines follow. Each of the t lines contains two space separated integers m and n with 0 ≤ m ≤ n ≤ 109.
Calculate am + am+1 + ... + an and print the result modulo 1000000007.
Input: 2 1 2 1919 5393 Output: 0 66616
Note: If your solution times out, you may try the tutorial version first.
Needs a lot of optimisations :) ... ac after many tle's
Very strict time limit. Had to remove unnecessary mod operations to AC. TLE otherwise.
Getting tle any suggestions??
Last edit: 2016-01-14 06:33:59
It was really very hard to get AC with my order_4 python3 solution, but now we can say it's possible !