Linear Recurrence for very large n

Posted by Android Decoded on Stack Overflow See other posts from Stack Overflow or by Android Decoded
Published on 2012-06-29T15:12:09Z Indexed on 2012/06/29 15:15 UTC
Read the original article Hit count: 268

Filed under:

recurrence

I was trying to solve this problem on SPOJ (http://www.spoj.pl/problems/REC/)

F(n) = a*F(n-1) + b where we have to find F(n) Mod (m) where

0 <= a, b, n <=  10^100
       1 <= M <= 100000

I am trying to solve it with BigInteger in JAVA but if I run a loop from 0 to n its getting TLE. How could I solve this problem? Can anyone give some hint? Don't post the solution. I want hint on how to solve it efficiently.

Related posts about recurrence

C#: Recurrence Calandar issue of Lotus notes

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi all, I am creating a Recurrence pattern in calendar items. But there is a issue as before clicking "Save and Send Invitations" button of Lotus notes 8.5, i am able to view the "RepeatForUnit" field from document property and based on its value i am identifying the Recurrence type like (D: for… >>> More
Finding recurrence relations of an algorithm

as seen on Stack Overflow - Search for 'Stack Overflow'
I'm reading my algorithms text book, and I'm reading about recurrence relations and finding the algorithms big O complexity. I run across this line "In the case of the merge-sort algorithm, we get the recurrence equation: t(n) = b if n < 2 = 2t(n/2) +bn … >>> More
Recurrence relation solution

as seen on Stack Overflow - Search for 'Stack Overflow'
I'm revising past midterms for a final exam this week and am trying to make sense of a solution my professor posted for one of past exams. (You can see the original pdf here, question #6). I'm given the original recurrence relation T(m)=3T(n/2) + n and am told T(1) = 1. I'm pretty sure the solution… >>> More
recurrence maths

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi all! I have the following: T(n) <= c floor(n/2) + c ceiling(n/2) + 1 = cn + 1 T(n) = O(n) I don't understand how it gets from the first equation to the second equation? What part of the maths am I missing to understand… >>> More
recurrence solution, too loose a bound?

as seen on Stack Overflow - Search for 'Stack Overflow'
I have the following worked out: T(n) = T(n - 1) + n = O(n^2) Now when I work this out I find that the bound is very loose. Have I done something wrong or is it just that way? >>> More

Developer IT

Linear Recurrence for very large n - Developer IT

Linear Recurrence for very large n

recurrence

Related posts about recurrence

C#: Recurrence Calandar issue of Lotus notes

Finding recurrence relations of an algorithm

Recurrence relation solution

recurrence maths

recurrence solution, too loose a bound?

Categories cloud