10229 - Modular Fibonacci

[caxibrema]

No the algorithm i used, each time divides n by 2 so is clearly log2(n)...

But i didt got the idea u used in the problem... do u process anything before and use it?

[Maarten]

Excuse me, that should be O(m), and not O(log(m)).. what I meant was O(log(2^m))....

That means I was talking about MY algorithm, and it means it's O(m) and not O(log(n)). Notice the difference between m and n please.

And yes, I precalculated fibonacci numbers up to 3*2^19

[oulongbin]

I don't know why my method is wrong,please help me,thanks.
[cpp]
get AC now!
[/cpp]

[dumb dan]

Your output is not quite correct for all inputs.
Try for example:

Input:

19000 19
123456 19

Correct output:

227947
64256

[wook]

Did you except that integer would be overflow?

64bit integer cannot save Fibonacci(2147483647) ....

Then you can use (a * b + c) % d = ((a % d) * (b % d) + c % d) %d


So, try modular operating in "O(logN) Fibonacci" Code.

You can get correct answer without using "BigInteger".

Thank You.

[oulongbin]

thank you very much!
i got AC used unsigned long long.

[CodeMaker]

Hi, is there any equation to find nth fibonacci? i think it will be stupid to find fibonacci(2147483647) even though i use modular arithematic by adding the previous two fibonacci numbers....there must be a formula, but unfortunately i dont know it. can anyone help?

[Larry]

You can either solve this problem by the Q-matrix method (google for it).

[Sedefcho]

My C++ program runs in 0.500 secs on this problem.

How do some people have 0.000 on this problem.

Is that possible?

I mean that in this problem we at least need some
serios pre-calculation. I do it in O (K), where K = 3*2^19.

Even if I do it in O ( log (K) ) / I think I read this is possible /,
I am sure I won't get that much of a speed-up ?!

So... How is 0.000 secs running time possible on this problem ?

Or... ? Am I misunderstanding something ?

[mf]

So... How is 0.000 secs running time possible on this problem ?

It is well-known and easy to prove by induction, that n-th powers of the
matrices [[0,1],[1,1]] and [[1,1],[1,0]] are:

[[0, 1], [1, 1]]^n = [[F(n-1), F(n)], [F(n), F(n+1)]]
[[1, 1], [1, 0]]^n = [[F(n+1), F(n)], [F(n), F(n-1)]]

(where F(n) is the n-th fibonacci number)

Since matrix multiplication is associative, to compute n-th matrix power
you can use the standard right-to-left exponentiation algorithm, with
all numbers computed modulo 0xFFFFF.
X^(2k) = (X*X)^k, X^(2k+1) = X * (X*X)^k

My own implementation of the above scheme ran 0.002 sec.

If you don't like matrices etc, you can also try to use the identities:

F(2n) = F(2n+1) - F(2n-1)
F(2n+1) = 4 * F(n)^2 - F(n-1)^2 + 2 * (-1)^n
F(2n-1) = F(n)^2 + F(n-1)^2

[Sedefcho]

Thanks for the hints. I will try them when I have some more
time to play with the Fibonacci Sequence. Thanks.

[sahand]

Hi guys, this is my code for 10229, and I just can't understand why I get WA's. It uses Q-matrix. It gives correct outputs for the samples and for anything else I checked. It would be great if someone could tell me what i'm doing is wrong. Thanks

------------ Problem solved thanks to mf -----------
What a stupid mistake it was, just missing f[0]=0
I couldn't possibly expect that they would put n=0 in the input..
anyway. I got AC in 0:00.004

[mf]

You missed one case:
F[0] = 0

[I LIKE GN]

USE BITWISE TO ACHIEVE 0.000
hope it helps
good luck
regards
RSS

[sklitzz]

Hi,
I'm having trouble with this task. I roamed througout the forum and figured out that I have to use modular arithmetic and qmatricies.
I know what modular arithmetic is but I never heared about q matricies, where can I find a good implementation and explanation about this. I already googled but couldn't find anything satisfactory.

TIA