A6087 | 「NOI2011」兔农
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
农夫栋栋近年收入不景气，正在他发愁如何能多赚点钱时，他听到隔壁的小朋友在讨论兔子繁殖的问题。
问题是这样的：第一个月初有一对刚出生的小兔子，经过两个月长大后，这对兔子从第三个月开始，每个月初生一对小兔子。新出生的小兔子生长两个月后又能每个月生出一对小兔子。问第 $n$ 个月有多少只兔子？
聪明的你可能已经发现，第 $n$ 个月的兔子数正好是第 $n$ 个 Fibonacci (斐波那契)数。栋栋不懂什么是 Fibonacci 数，但他也发现了规律：第 $i+2$ 个月的兔子数等于第 $i$ 个月的兔子数加上第 $i+1$ 个月的兔子数。前几个月的兔子数依次为：
$$ 1, 1, 2, 3, 5, 8, 13, 21, 34 \dots $$
栋栋发现越到后面兔子数增长的越快，期待养兔子一定能赚大钱，于是栋栋在第一个月初买了一对小兔子开始饲养。 每天，栋栋都要给兔子们喂食，兔子们吃食时非常特别，总是每 $k$ 对兔子围成一圈，最后剩下的不足 $k$ 对的围成一圈，由于兔子特别害怕孤独，从第三个月开始，如果吃食时围成某一个圈的只有一对兔子，这对兔子就会很快死掉。 我们假设死去的总是刚出生的兔子，那么每个月的兔子数仍然是可以计算的。例如，当 $k=7$ 时，前几个月的兔子数依次为：
$$ 1, 1, 2, 3, 5, 7, 12, 19, 31, 49, 80 \dots $$
给定 $n$ ，你能帮助栋栋计算第 $n$ 个月他有多少**对**兔子么？由于答案可能非常大，你只需要告诉栋栋第 $n$ 个月的兔子对数除 $p$ 的余数即可。
问题是这样的：第一个月初有一对刚出生的小兔子，经过两个月长大后，这对兔子从第三个月开始，每个月初生一对小兔子。新出生的小兔子生长两个月后又能每个月生出一对小兔子。问第 $n$ 个月有多少只兔子？
聪明的你可能已经发现，第 $n$ 个月的兔子数正好是第 $n$ 个 Fibonacci (斐波那契)数。栋栋不懂什么是 Fibonacci 数，但他也发现了规律：第 $i+2$ 个月的兔子数等于第 $i$ 个月的兔子数加上第 $i+1$ 个月的兔子数。前几个月的兔子数依次为：
$$ 1, 1, 2, 3, 5, 8, 13, 21, 34 \dots $$
栋栋发现越到后面兔子数增长的越快，期待养兔子一定能赚大钱，于是栋栋在第一个月初买了一对小兔子开始饲养。 每天，栋栋都要给兔子们喂食，兔子们吃食时非常特别，总是每 $k$ 对兔子围成一圈，最后剩下的不足 $k$ 对的围成一圈，由于兔子特别害怕孤独，从第三个月开始，如果吃食时围成某一个圈的只有一对兔子，这对兔子就会很快死掉。 我们假设死去的总是刚出生的兔子，那么每个月的兔子数仍然是可以计算的。例如，当 $k=7$ 时，前几个月的兔子数依次为：
$$ 1, 1, 2, 3, 5, 7, 12, 19, 31, 49, 80 \dots $$
给定 $n$ ，你能帮助栋栋计算第 $n$ 个月他有多少**对**兔子么？由于答案可能非常大，你只需要告诉栋栋第 $n$ 个月的兔子对数除 $p$ 的余数即可。
输入格式
输入一行，包含三个正整数 $n, k, p$ 。
输出格式
输出一行，包含一个整数，表示栋栋第 $n$ 个月的兔子对数除 $p$ 的余数。
输入输出样例
输入 #1
6 7 100
输出 #1
7
输入 #2
7 7 5
输出 #2
2
| 测试点编号 | $n$ | $k,p$ |
| :-: | :-: | :-: |
| 1 | $1 \le n \le 50$ | $2 \le k,p \le 1000$ |
| 2 | $1 \le n \le 50$ | $2 \le k,p \le 1000$ |
| 3 | $1 \le n \le 50$ | $2 \le k,p \le 1000$ |
| 4 | $1 \le n \le 50$ | $2 \le k,p \le 1000$ |
| 5 | $1 \le n \le 50$ | $2 \le k,p \le 1000$ |
| 6 | $1 \le n \le 50$ | $2 \le k,p \le 1000$ |
| 7 | $1 \le n \le 50$ | $2 \le k,p \le 1000$ |
| 8 | $1 \le n \le 50$ | $2 \le k,p \le 1000$ |
| 9 | $1 \le n \le 50$ | $2 \le k,p \le 1000$ |
| 10 | $1 \le n \le 50$ | $2 \le k,p \le 1000$ |
| 11 | $1 \le n \le 80$ | $2 \le k,p \le 10,000$ |
| 12 | $1 \le n \le 1000$ | $2 \le k,p \le 10,000$ |
| 13 | $1 \le n \le 1000$ | $2 \le k,p \le 10,000$ |
| 14 | $1 \le n \le 10^6$ | $2 \le k,p \le 10^6$ |
| 15 | $1 \le n \le 10^6$ | $2 \le k,p \le 10^6$ |
| 16 | $1 \le n \le 10^{18}$ | $2 \le k,p \le 1000$ |
| 17 | $1 \le n \le 10^{18}$ | $2 \le k,p \le 1000$ |
| 18 | $1 \le n \le 10^{18}$ | $2 \le k \le 10^6,2 \le p \le 10^9$ |
| 19 | $1 \le n \le 10^{18}$ | $2 \le k \le 10^6,2 \le p \le 10^9$ |
| 20 | $1 \le n \le 10^{18}$ | $2 \le k \le 10^6,2 \le p \le 10^9$ |
| :-: | :-: | :-: |
| 1 | $1 \le n \le 50$ | $2 \le k,p \le 1000$ |
| 2 | $1 \le n \le 50$ | $2 \le k,p \le 1000$ |
| 3 | $1 \le n \le 50$ | $2 \le k,p \le 1000$ |
| 4 | $1 \le n \le 50$ | $2 \le k,p \le 1000$ |
| 5 | $1 \le n \le 50$ | $2 \le k,p \le 1000$ |
| 6 | $1 \le n \le 50$ | $2 \le k,p \le 1000$ |
| 7 | $1 \le n \le 50$ | $2 \le k,p \le 1000$ |
| 8 | $1 \le n \le 50$ | $2 \le k,p \le 1000$ |
| 9 | $1 \le n \le 50$ | $2 \le k,p \le 1000$ |
| 10 | $1 \le n \le 50$ | $2 \le k,p \le 1000$ |
| 11 | $1 \le n \le 80$ | $2 \le k,p \le 10,000$ |
| 12 | $1 \le n \le 1000$ | $2 \le k,p \le 10,000$ |
| 13 | $1 \le n \le 1000$ | $2 \le k,p \le 10,000$ |
| 14 | $1 \le n \le 10^6$ | $2 \le k,p \le 10^6$ |
| 15 | $1 \le n \le 10^6$ | $2 \le k,p \le 10^6$ |
| 16 | $1 \le n \le 10^{18}$ | $2 \le k,p \le 1000$ |
| 17 | $1 \le n \le 10^{18}$ | $2 \le k,p \le 1000$ |
| 18 | $1 \le n \le 10^{18}$ | $2 \le k \le 10^6,2 \le p \le 10^9$ |
| 19 | $1 \le n \le 10^{18}$ | $2 \le k \le 10^6,2 \le p \le 10^9$ |
| 20 | $1 \le n \le 10^{18}$ | $2 \le k \le 10^6,2 \le p \le 10^9$ |
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？