10689 - Yet another Number Sequence
Moderator: Board moderators
10689 - Yet another Number Sequence
I getting WA with this problem but I think that my solution is OK.
My algorithm:
I use matrix chain multiplication.
I send my solution to p10229( Modular Fibonacci ) and I got Accepted.
Are there any tricks?
My algorithm:
I use matrix chain multiplication.
I send my solution to p10229( Modular Fibonacci ) and I got Accepted.
Are there any tricks?
My case is, I used my old code from 10229, but keep getting WA.
At last, I found my code of 10229 is wrong, though it is accetped.......
At last, I found my code of 10229 is wrong, though it is accetped.......
My signature:
- Please make discussion about the algorithm BRFORE posting source code.
We can learn much more in discussion than reading source code. - I HATE testing account.
- Don't send me source code for debug.
If you know "Pisano period" then you can solve the problem very easily.
The last digit of Fibonacco number repeats with a period of 60. The last
two digits repeat with a period of 300, the last three with a period of
1500 and the last four digits have a period of 15000.
See the following link:
http://mathworld.wolfram.com/PisanoPeriod.html
The last digit of Fibonacco number repeats with a period of 60. The last
two digits repeat with a period of 300, the last three with a period of
1500 and the last four digits have a period of 15000.
See the following link:
http://mathworld.wolfram.com/PisanoPeriod.html
i read your post, read about pisano period, and try to solve this problem, but always got WA. however i'm not sure is pisano period valid for all a and b (i mean f[0]=a, f[1]=b)? or just for a=0 & b=1?
thank you in advance.
-natalya-
Code: Select all
--cut---
-natalya-
Last edited by natalya on Mon Aug 16, 2004 5:39 pm, edited 1 time in total.
Go Natalya!
not valid for all (a,b) pairs. there's nothing profound about the number 15000; this number changes as a,b, or m changes.
i used this 'pisano period' method (but at the time i submitted didn't realize it was even called that until i see this thread now). just figure that the last m digits of fib(n-1),fib(n) determine the last m digits of fib(n+1), so the sequence has to be periodic with period at *most* 10^{2m}. i experimented to see what the period was for m = 10^4 and luckily it just happened to be 15,000 (instead of something like 10^8 which would have sucked
).
the trick is realizing that (except for val[0]=a), val in your array can be expressed as p*a + q*b where p and q work out nicely. i used this to get ac in .037s. see my hint post above and hopefully you'll realize what i mean.
good luck.
i used this 'pisano period' method (but at the time i submitted didn't realize it was even called that until i see this thread now). just figure that the last m digits of fib(n-1),fib(n) determine the last m digits of fib(n+1), so the sequence has to be periodic with period at *most* 10^{2m}. i experimented to see what the period was for m = 10^4 and luckily it just happened to be 15,000 (instead of something like 10^8 which would have sucked
![:-?](./images/smilies/icon_confused.gif)
the trick is realizing that (except for val[0]=a), val in your array can be expressed as p*a + q*b where p and q work out nicely. i used this to get ac in .037s. see my hint post above and hopefully you'll realize what i mean.
good luck.
-
- Guru
- Posts: 584
- Joined: Thu Jun 19, 2003 3:48 am
- Location: Sanok, Poland
- Contact:
I find matrix method the best. Counting power of a proper 2x2 matrix allows to get n-th value of sequence f(n) = p * f(n - 1) + q * f(n - 2) for any p, q and for any starting value. I solved many problems doing copy-paste and simply changing the constants.
For the simple case here it's enough to find
Of course to find the power one should use O(log n) algorithm.
For the simple case here it's enough to find
Code: Select all
|a, b | * |0, 1|^n mod m
|b, a + b| |1, 1|
I think it depends what you mean by best. I used this first also because I already had it pre-coded from doing other fibonacci-type problems. But this method runs slower than the periodic method, and it is also more lines to code if you don't have it coded up already.I find matrix method the best...
-
- Guru
- Posts: 584
- Joined: Thu Jun 19, 2003 3:48 am
- Location: Sanok, Poland
- Contact:
In my opinion, the biggest strength of the matrix method compared to the period method is the asymptotic complexity. In this problem, the period was quite small, but the maximum moduli could just as easily have been set to say, 10^9, and the period method would never have worked. In order to make the matrix method inapplicable, you'll have to use Really Really Big(tm) values of n, which I doubt will happen in a contest problem.
(Nonetheless, this was actually the first problem where I used the matrix method for computing fibonacci numbers)
(Nonetheless, this was actually the first problem where I used the matrix method for computing fibonacci numbers)
-
- Guru
- Posts: 584
- Joined: Thu Jun 19, 2003 3:48 am
- Location: Sanok, Poland
- Contact:
Natalya:
You did a very silly mistake.
Just check your code's output for the following input:
I think now you will be able to find your fault.
Also note that Pisano period is valid for all a and b.
You did a very silly mistake.
Just check your code's output for the following input:
Code: Select all
1
10 12 1 1
Also note that Pisano period is valid for all a and b.