10229  Modular Fibonacci
Moderator: Board moderators
10229 help!
I don't know why my method is wrong,please help me,thanks.
[cpp]
get AC now!
[/cpp]
[cpp]
get AC now!
[/cpp]
Last edited by oulongbin on Tue Oct 05, 2004 4:51 am, edited 1 time in total.
Oh..
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.
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.
Sorry For My Poor English..
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 precalculation. 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 speedup ?!
So... How is 0.000 secs running time possible on this problem ?
Or... ? Am I misunderstanding something ?
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 precalculation. 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 speedup ?!
So... How is 0.000 secs running time possible on this problem ?
Or... ? Am I misunderstanding something ?
It is wellknown and easy to prove by induction, that nth powers of theSedefcho wrote: So... How is 0.000 secs running time possible on this problem ?
matrices [[0,1],[1,1]] and [[1,1],[1,0]] are:
[[0, 1], [1, 1]]^n = [[F(n1), F(n)], [F(n), F(n+1)]]
[[1, 1], [1, 0]]^n = [[F(n+1), F(n)], [F(n), F(n1)]]
(where F(n) is the nth fibonacci number)
Since matrix multiplication is associative, to compute nth matrix power
you can use the standard righttoleft 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(2n1)
F(2n+1) = 4 * F(n)^2  F(n1)^2 + 2 * (1)^n
F(2n1) = F(n)^2 + F(n1)^2

 New poster
 Posts: 19
 Joined: Sat Mar 12, 2005 5:56 pm
 Location: Halifax, Nova Scotia, Canada
 Contact:
10229  WA  please help
Hi guys, this is my code for 10229, and I just can't understand why I get WA's. It uses Qmatrix. 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
 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
Last edited by sahand on Sun Mar 13, 2005 3:24 am, edited 2 times in total.

 Learning poster
 Posts: 57
 Joined: Fri Oct 10, 2003 11:01 pm
 Location: in front of PC
 Contact:
to achieve 0.00000000
USE BITWISE TO ACHIEVE 0.000
hope it helps
good luck
regards
RSS
hope it helps
good luck
regards
RSS
There are two tragedies in life one is to lose your hearts' desire and another is to gain it  GBS.
10229 Modular Fibonacci
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
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