兔农
测试数据来自 system/1722
描述
农夫栋栋近年收入不景气,正在他发愁如何能多赚点钱时,他听到隔壁的小朋友在讨论兔子繁殖的问题。 问题是这样的:第一个月初有一对刚出生的小兔子,经过两个月长大后,这对兔子从第三个月开始,每个月初生一对小兔子。新出生的小兔子生长两个月后又能每个月生出一对小兔子。问第 n个月有多少只兔子?
聪明的你可能已经发现,第n个月的兔子数正好是第 n个Fibonacci(斐波那契)数。栋栋不懂什么是 Fibonacci 数,但他也发现了规律:第 i+2 个月的兔子数等于第i 个月的兔子数加上第 i+1个月的兔子数。前几个月的兔子数依次为:
1 1 2 3 5 8 13 21 34 …
栋栋发现越到后面兔子数增长的越快,期待养兔子一定能赚大钱,于是栋栋在第一个月初买了一对小兔子开始饲养。 每天,栋栋都要给兔子们喂食,兔子们吃食时非常特别,总是每 k对兔子围成一圈,最后剩下的不足 k对的围成一圈,由于兔子特别害怕孤独,从第三个月开始,如果吃食时围成某一个圈的只有一对兔子,这对兔子就会很快死掉。 我们假设死去的总是刚出生的兔子,那么每个月的兔子数仍然是可以计算的。
例如,当k=7 时,前几个月的兔子数依次为:
1 1 2 3 5 7 12 19 31 49 80 …
给定 n,你能帮助栋栋计算第 n个月他有多少对兔子么?由于答案可能非常
大,你只需要告诉栋栋第 n个月的兔子对数除 p的余数即可。
格式
输入格式
输入一行,包含三个正整数 n, k, p。
输出格式
输出一行,包含一个整数,表示栋栋第 n个月的兔子对数除p 的余数。
限制
各个测试点1s
提示
测试点1~10: 1<=n<=50, 2<=k,p<= 1000
测试点11: 1<=n<= 80, 2<=k,p<=10000
测试点12,13: 1<=n<=1000, 2<=k,p<=10000
测试点14,15: 1<=n<=10^6, 2<=k,p<=10^6
测试点16,17: 1<=n<=10^18, 2<=k,p<=1000
测试点18~20: 1<=n<=10^18, 2<=k<=10^6, 2<=p<=10^9
来源
NOI 2011 DAY1 rabbit
信息
- ID
- 1663
- 难度
- (无)
- 分类
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 通过率
- ?
- 上传者