what i am trying to do is res[x]=res[x-1]+res[x-1]+cnt
cnt begins at 1.
x can be as large as 1000000
i need to o/p the answer as %1000000007
what m doing is res[x]=(res[x-1]+res[x-1]+cnt)%MOD
this isn’t the right approach probably, everytime i see the MOD operator I always get a nervous break down. Is there any specific approach to solve the problems involving MOD operator??
That quite depends upon the problem statement. You might come across different situations where even finding modulo itself needs an algorithm to be efficient enough to solve the problem. For God’s sake, we have some good and popular algorithms which make the work for us. Few of them are
- Fermat’s little theorem
- Fast Modular Exponentiation
- Modular multiplicative inverse
which you might find useful for solving most the problems involving Modulo operation for large numbers.Here are some useful links for you to get startedhttp://en.wikipedia.org/wiki/Fermat%27s_little_theoremhttp://en.wikipedia.org/wiki/Modular_exponentiationhttp://en.wikipedia.org/wiki/Modular_multiplicative_inverse
Once you got to feel comfortable with the actual algorithm, try to implement them in your preferred language.
Some problems may include much complex logics behind to solve modularity. But, try to have a good understanding of the problem before actually worrying about the coding.
I have seen your former question about (a/b)%c != (a)%c/b. This needs to be solved using Modular Multiplicative Inverse and hence updated my answer @apurvjain17
Here overflow may occur so try to module MOD by each variable.
(a * b) MOD is same as ( (a MOD) * (b MOD) ) MOD
(a + b) MOD is same as ( (a MOD) + (b MOD) ) MOD
For this expression, res[x]=res[x-1]+res[x-1]+cnt
Perform this operation
res[x] = ( (res[x-1] MOD) + (res[x-1] MOD) + (cnt MOD) ) MOD;
But for division rules are different.