Could someone provide hint/editorial for this question
http://www.codechef.com/IOPC2014/problems/IOPC14F
Its mentioned everywhere that there is no general formula to find pisano period http://en.wikipedia.org/wiki/Pisano_period
Then how to solve this problem?
I solved it using pisano period’s multiple number, but it took hard and the solution may be not elegant.
I noticed a fact after the contest. I give you a hint.
If we can represent C(n,r) with some numbers’ product(=a1 * a2 * a3 * …), this problem can be solved by calculating
[[1,1],[1,0]]^(a1 * a2 * a3 * …) mod M
=(…((([[1,1],[1,0]]^a1)^a2)^a3)^…) mod M
OK?
you can factorize n! into prime factors. Guess the rest.
The Pisano period approach is not so hard, but lengthy - you need basically everything from basic number theory.
We can compute Fibonacci numbers by matrix exponentiation. What’s the result of multiplying (vertical lines denote matrices, not determinants)
|1 1| |x|
|1 0| |y| ?
There is no formula for the Pisano period, but then again, if there was, this wouldn’t really be a programming question :D. There are several theorems that can help us: Chinese remainder theorem states that if you decompose M into a product of prime powers, then the period is just LCM of periods modulo those prime powers; for a prime power p^a (a > 1), the period pi(p^a) will be p^(a-1) * pi§ (this doesn’t hold generally, but so far no number for which it doesn’t hold has been found, and we can hope that the contest organizers didn’t make a massive discovery in mathematics :D), and for a prime p, the period pi§ will divide either p-1 or 2 * (p+1) for every p except 2 and 5 (for which finding the period is trivial). You can just bruteforce all divisors of p-1 and 2*(p+2), then, and choose the smallest period.
All that’s left now is to compute nCr modulo pi(M). nCr=n!/r!(n-r)!; for every prime factor of pi(M), find which power of it divides nCr, compute “reduced” n!, r! and (n-r)! %pi(M) after dividing them by maximum powers of those prime factors, compute the modular inverse of reduced r!(n-r)!, compute the reduced nCr and multiply it back by the correct powers of prime factors of pi(M). All of it mod pi(M). Then just find its corresponding Fibonacci number.
@xellos0 nice explanation…
where u come across this theorem “Chinese remainder theorem states that if you decompose M into a product of prime powers, then the period is just LCM of periods modulo those prime powers”?
Just google (UTFG) Chinese remainder theorem. There’s a wikipedia page, a proof on it, and definitely several articles about it. It’s a pretty famous theorem.
by matrix exponentiation i think we will get tle?
@prakashjaggi You can use fast doubling .Its faster than matrix exponentation method http://nayuki.eigenstate.org/page/fast-fibonacci-algorithms
I meant matrix exponentiation by squaring.