Cant understand recursive sequence 2 (SPP), https://www.spoj.com/problems/SPP/

#1

i understood the normal matrix exponentiation problem, but in this since i have to calculate sum of terms , i cant get logic to do so, each time i have to calculate the next term each time i have to build the transformation matrix and also, if i go from n=1 to m=10^18 terms and maintain their sum, then also time complexity will be out of limit, so please help me understand this problem, through hint i dont understand this problem

#2

@mehul.narendra.dubey,
Yes, you have a valid point that if you use matrix exponentiation to find the n_{th} term, and then sum of each such term in asked range, it would give TLE, but as bhaiya pointed out in hint, use matrix exponentiation to calculate the sum of n terms, then you can simply calculate answer by
sum_r-sum_{l-1} .
The recurrence for calculating the sum of first n terms directly was shown in hint video.

#3

for this i have to calculate sum( r ), and sum( r ) = sum(r-1) + a(n), i can build transformation matrix if and only if i have sum, how to store them, and if i calculate sum one by one without matrix exponentiation it will again result in TLE

#4

@mehul.narendra.dubey,
See the recurrence shown by bhaiya in hint video, it gives sum(r) in O(logn).

#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.