Is there a way to do this?

# | User | Rating |
---|---|---|

1 | Um_nik | 3538 |

2 | tourist | 3509 |

3 | Benq | 3473 |

4 | ecnerwala | 3446 |

5 | ksun48 | 3432 |

6 | maroonrk | 3404 |

7 | Radewoosh | 3383 |

8 | yosupo | 3324 |

9 | boboniu | 3300 |

10 | apiadu | 3238 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 207 |

2 | Monogon | 199 |

3 | SecondThread | 191 |

4 | vovuh | 188 |

5 | antontrygubO_o | 185 |

5 | pikmike | 185 |

7 | Um_nik | 184 |

8 | Ashishgup | 182 |

9 | pashka | 168 |

9 | Radewoosh | 168 |

Is there a way to do this?

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/21/2020 22:31:26 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Yes, there is.

Yes, there is. Think about the formula...

F_{i}=F_{i - 1}+F_{i - 2}= 2 *F_{i - 2}+F_{i - 3}= 3 *F_{i - 3}+ 2 *F_{i - 4}....If you keep on with the formula, assuming

F_{0}= 1 andF_{1}= 1, you'll reach a point where...(if

iis even)(if

iis odd)Or, generalizing for every

i...Using those formulas and a recursive function with memoization, you can run the algorithm in no time.

The implementation is very short and simple. Check it out here -> Fibonacci

i can't understand how it works if u call with fib(n+1) it never meet with base case...plz explain

The recursive function doesn't call fib(n+1), it calls fib((n+1) / 2).

ooo sorry i saw wrong,,,that's my eye mistake sorry

That is interesting.

Is this for Fibonacchi Numbers only?

What do you mean? It's a function that calculates the

n_{th}Fibonacci number inO(log_{n}).Generally we do these things by matrix exponentiation.

What I meant to ask is whether it is possible for all such problems to find some formula and solve it. Like you did.

Ahhhhh, I see. I don't know about matrix exponentiation. I always found it very hard and never decided to actually study about it.

I knew Fibonacci numbers could be calculated using matrix exponentiation, but since that's beyond my understanding, I decided to try and find my own method. I did, and I must say I find this method much easier to understand, easier to code and maybe even faster.

I don't know if there's a general formula for other problems that use matrix exponentiation too. I think that there might some that can be solved by a formula and also many others that can't.

If you can formulate your number like , you can solve it using matrix exponentiation. This is a nice article about it!

Thanks for mentioning my blog post! I almost forgot that such post exists :P

Always,when you can present your sequence member using lower grade sequence numbers,you can calculate it in same way,as describe tenshi_kanade

for example: if F(n)=F(n/3)*F(n/3+1)+x you can calculate in O(2^log(3,n))

So we don't actually need matrix exponentiation for such kind of problems? :P

yes,we don't

I instantly thought of Matrix Exponentiation when I read the statement...

But this method is even easier and prettier... m(_ _)m

By the way can anyone say how to calculate Pisano period fast?

There is formulae for prime powers. So you need only factorize modulo.

What formulae?

For p=5^k pisano period is a divisor of 5^k; For p quadratic residue modulo 5 pisano period is a divisor of (p-1)p^{k-1}; For p quadratic nonresidue modulo 5 pisano period is a divisor of 2(p+1)p^{k-1}

I'm not sure about this, but you may test it. The formula for the n-th Fibonacci number is

If we write the

`pow`

function to be fast modulo exponentiation this gives us`O(logN)`

complexity.UPD:This function might not work with double arguments, so this is hardly a right solution.This formula is applicable iff 5 is a quadratic residue modulo

pandpis prime. We can check it using Euler's criterion.For example, let's take

p= 10^{9}+ 9. Euler's criterion is true: . That means we can find a square root of 5 modulop.Let's find it. I prefer Wolfram Alpha:

`powermod[5,1/2,10^9+9] = 383008016`

. We can insert this number into your formula, and the final result isF_{n}= 276601605·(691504013^{n}- 308495997^{n})So this actually works?

Still can't understand where did you get all the numbers in the formula.

They do this by finding some number

xsuch that . This is like the in . It turns out that forp= 10^{9}+ 9, thisxactually exists and isx= 383008016, which you can find out using Wolfram Alpha. They then substitute 383008016 for in your formula and simplify to get those numbers.If I am not mistaken, you can do same thing for all modules not equal to 5 by adding roots of

x^{2}- 5 to if 5 is not quadratic residue . I mean, calculate value of the same formula on numbers of typea+bx, where and with rules of addition and multiplication similar to complex numbers (result will always be free of "imaginary" part):I guess you are right. The thing is the expression never contains square root of five. So we don't really care whether it even exists. It is nice if it does, but it is totally unnecessary. For example my program (link) can calculate Fibonacci numbers modulo 3^6*7^2=35721. And there is no x such that x*x=5 mod 35721. The trick is to work with numbers, similar to complex, with only one difference that i*i=5, not -1.

Nevertheless you can actually use this formula to calculate Fibonacci numbers modulo any odd number. You just need to calculate it not with the help of doubles, but numbers of the form . They have properties similar to complex numbers. For example the product of two numbers equals .

And because of special structure of this formula, the answer is , where

Imtakes the part right next to square root of five (I called it so because of similarity with complex numbers). So you only need to be able to divide by two and that can be done modulo any odd number.Matrix exponentiation

Yes. See this page.

You came and gave a problem: Calculate Fib(n)=Fib(n-1)+Fib(n-2) % M in O(logN). Cool.

Now I come and give you a challenge: SuperFib(n)=A*SuperFib(n-1)+B*SuperFib(n-2)+C*SuperFib(n-3) % M (SuperFib(0), SF(1), SF(2) are given, as well as A, B and C). Solve it in O(logN) time. This requires matrix exponential. If you want to learn something great.

This

You could use matrix multiplication here, to get to the Nth number in log(N) time. Here is a video tutorial explaining the same: Fibonacci Numbers using Matrix Multiplication

This is a 2 year old post. Idiot

:)

be polite :(