SPOJ.com - Problem FRSKT

FRSKT - Fibonacci recursive sequences (medium)

no tags

Let FIB the Fibonacci function :
FIB(0)=0 ; FIB(1)=1
and
for N>=2 FIB(N) = FIB(N-1) + FIB(N-2)

Example : we have FIB(6)=8, and FIB(8)=21.

Let F(K, N) a new function:
F(0, N) = N for all integers N.
F(K, N) = F(K-1, FIB(N) ) for K>0 and all integers N.

Example : F(2, 6) = F(1, FIB(6) ) = F(0, FIB( FIB(6) ) ) = FIB( FIB(6) ) = FIB(8) = 21

Input

The input begins with the number T of test cases in a single line.
In each of the next T lines there are three integers: K, N, M.

Output

For each test case, print F(K, N),
as the answer could not fit in a 64bit container,
give your answer modulo M.

Example

Input:
3
4 5 1000
3 4 1000
2 6 1000

Output:
5
1
21

Constraints

1 <= T <= 10^3
0 <= K <= 10^2
0 <= N <= 10^9
2 <= M <= 10^9

You would perhaps have a look, after, at the hard edition with more difficult constraints.

Edit 2017-02-11, after compiler update. My old Python code ends in 0.08s. New TL.

Submit solution!

hide comments

< Previous 1 2 Next >

	DK...: 2019-06-05 23:52:20 I got AC in the harder version and the same code got WA for this problem, @Francky please, could you tell me what is happening with the testcases? =(Francky)=> You have WA on some corner cases. Check them all. Look again at constraints. =(DK...)=> Thanks a lot bro!. Finally I got AC. Last edit: 2020-04-01 18:22:48
	Gaurav Kumar Verma: 2014-11-03 09:56:03 can anyone please provide sample test cases? m getting WA --ans(Francky)--> You can build them on your own, with a python brute force for example, or even in C/C++ with very small moduli. No other test cases are provided. Good luck. Last edit: 2014-11-03 13:55:41
	[Lakshman]: 2014-07-14 11:09:19 @SHUBHAM JAIN try to solve some easy Fibonacci problem then come to this. try FIBTWIST,FIBOSUM..
	SHUBHAM JAIN: 2014-07-14 10:36:38 I am getting Segmentation fault runtime error in your compiler but it is running properly in my compiler
	[Lakshman]: 2014-06-25 10:59:50 @Francky My new solution seems to be fine for all corner cases, but still getting WA. can you please give me some hint where my new solution fails. Thanks. --ans(Francky)--> There's a last corner. For two cases ,in my input file, your output is 0, but answer is not 0. Good luck, you're not so far. Lakshman-->Thanks @Francky for this awesome problem. learned a lot from this. --ans(Francky)--> As you can see in timings, you still have many secrets to be found for that kind of problems. The game is far from over. Good job, and thanks for your appreciation. --Lakshman-->Actually my solution depends on some brute force while computing Pio. Thanks for the time limit. I will work on my faster algorithm and try to find out the bug in my faster algorithm. --Lakshman-->Final optimization and its .21s Last edit: 2014-07-14 15:34:43**
	[Lakshman]: 2014-03-02 22:30:37 @Francky can you please check my solution why I am getting runtime error. Thanks --ans(Francky)--> Your code is complex and not easy to read, I don't have more info by the judge. Good luck. Last edit: 2014-03-02 23:43:14
	fR0DDY: 2013-08-03 10:58:17 I am getting Runtime Error. Any hints for my solution or is my solution completely wrong?
	[Lakshman]: 2013-05-12 07:06:57 Can you please give a bit hint where my solution fails ....... --ans--> You should try FRS2 first, your logic is wrong. Last edit: 2013-05-12 07:39:52
	(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†): 2013-01-21 03:01:43 finally #1st place on this problem ;-) --ans--> Good job, but the problem still keeps some secrets for a really serious boost... EDIT: Thanks for the info, I have new idea, but only boost 0.08s.. for now my best is 0.22s.. Last edit: 2013-01-22 22:14:44
	(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†): 2012-09-05 18:20:13 I'm getting WA... any clues/hints? --ans--> I didn't took a good look, but I can say now that you have some few good answers, so it could be a vicious overflow, if I have time I'll take a better look. It's yet a good job. Why don't you build a Python version to track those issues ? Edit : you have some issues even with small input (n,m under 100, and k=2). You should test with a python brute force to find some "secrets", there's a lot to find. RE: Thanks for your hints, Python brute-force really help me finding my mistake :-D Last edit: 2012-09-06 02:56:03

Submit solution!

Added by:	Francky
Date:	2012-08-19
Time limit:	0.5s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64
Resource:	Own problem