P2020 [NOI2011]兔农

    • 110通过
    • 431提交
  • 题目提供者 洛谷
  • 评测方式 云端评测
  • 标签 数论,数学 斐波那契,Fibonacci 逆元 NOI系列 2011 高性能
  • 难度 NOI/NOI+/CTSC
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    农夫栋栋近年收入不景气,正在他发愁如何能多赚点钱时,他听到隔壁的小朋友在讨论兔子繁殖的问题。

    问题是这样的:第一个月初有一对刚出生的小兔子,经过两个月长大后,这对兔子从第三个月开始,每个月初生一对小兔子。新出生的小兔子生长两个月后又能每个月生出一对小兔子。问第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的余数。

    输入输出样例

    输入样例#1: 复制
    6 7 100
    输出样例#1: 复制
    7
    输入样例#2: 复制
    7 75
    输出样例#2: 复制
    2

    说明

    1<=n<=10^18

    2<=k<=10^6

    2<=p<=10^9

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。