所属专题：[组合数学](README.md)；[动态规划](README.md)
 
## 问题
在著名的“斐波那契兔子”问题中，有如下的假定：
1. 兔子种群在第一个月从一对新生的兔子开始；
2. 兔子们在出生一个月后达到生育年龄；
3. 在任何一个月，每一只育龄兔子会与另一只育龄兔子交配；
4. 兔子交配后一个月，会生下一对兔子（一只雄兔与一只雌兔）；
5. 不考虑兔子寿命限制，兔子会一直繁殖下去。
在这里，我们对“斐波那契兔子”问题进行推广，每对兔子交配后一个月，将产下`$ k $`对兔子，求解若干个月后的兔子总对数。
**输入：** 两个正整数`$ n\le40 $`与`$ k\le5 $`。
**输出：** 第`$ n $`个月时兔子的总对数。假定我们从1对兔子开始，在每一代，一对兔子会生下`$ k $`对兔子（而不是原始“斐波那契兔子”问题中的1对）。
**样例数据：**
```
5 3
```
**样例输出：**
```
19
```
 
## 背景知识
这个问题来源于历史上著名的数学问题“斐波那契兔子”问题。在原问题的设定中，兔子数量随时间（代际）发展的变化如下图所示：（图片来源：[ROSALIND](http://rosalind.info/media/problems/fib/)）
*****
<div align="center"><img src="http://rosalind.info/media/problems/fib/rabbit_tree.thumb.png"></div>
<div align="center">斐波那契兔子数量在前六个月的增长图示</div>
*****
斐波那契兔子问题还涉及递推数列等数学问题。详情请查阅ROSALIND网站上[关于该问题的背景说明](http://rosalind.info/problems/fib/)。
 
## 解答
```
def fib_new(n, k):
"""给定兔子代数n与单次繁殖数k，遵循斐波那契规则，计算n代兔子的总数"""
num = [0, 1, 1]
for i in range(3, n+1):
num.append(k*num[i-2]+num[i-1])
return num[n]
## --main--
with open("rosalind_fib.txt", 'r') as f1:
n,k = map(int, f1.read().split())
with open("rosalind_fib_out.txt", 'w') as f2:
f2.write(str(fib_new(n, k)))
```
