## 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.

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!

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.

good luck.

- Krzysztof Duleba
- 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...

- Krzysztof Duleba
- Guru
**Posts:**584**Joined:**Thu Jun 19, 2003 3:48 am**Location:**Sanok, Poland-
**Contact:**

(Nonetheless, this was actually the first problem where I used the matrix method for computing fibonacci numbers)

- Krzysztof Duleba
- Guru
**Posts:**584**Joined:**Thu Jun 19, 2003 3:48 am**Location:**Sanok, Poland-
**Contact:**

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.