a817: 短命兔子~費氏數列(3)
標籤 : dp fibonacci
通過比率 : 2人/6人 ( 33% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-10-09 17:50

內容

感謝$11th$進階教學郭勝威讓我的題目可以借用他的系列來出題 (a814簡單的費氏數列(1)a815神奇的費氏數列(2)

樓梯是不是已經走膩了呢,來換換口味吧?

大家在學習費氏數列時,一定都聽過數學老師利用費波納契提出的兔子繁殖情形來講解這個數列。

簡單來說,有四個條件:

1. 第一個月,有一隻小兔。

2. 每過一個月,小兔成長為大兔。

3. 對這些無敵的兔子來說,沒有老、病、死等問題。

4. 大兔不會再生長,但每隻大兔每個月都可以生出一隻小兔,且不限年齡為何皆可以生殖。

有沒有覺得這些兔子有點太強了,這樣下去地球一定都充滿了兔子!大家都習慣了不死的兔子,所以這一題來點不一樣的:

兔子平均壽命約$5$至$12$歲,最老的甚至活到了$18$歲。假定他們每一隻兔子都非常健康 (不會病死) ,每一隻都可以活$K$個月(第一隻小兔死在第$K+1$個月中,而且在第$K$個月時他依舊可以生殖,以此類推),請問你在第$N$個月時,兔子總數為何?

輸入說明

多個測資點,每筆測資中第一行有兩個正整數$T$、$K$

接下來$T$行中問第$N$個月時兔子的數量為何?

輸出說明

輸出一個正整數代表那個月兔子的總數 ($mod10^9+7$)

範例輸入
5 100
1
2
3
4
5
範例輸出
1
1
2
3
5
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (20%): 1.0s , <1M
公開 測資點#1 (30%): 1.0s , <10M
公開 測資點#2 (50%): 1.0s , <50M
提示 :

兔子的數量不會是負數對吧~

$N,T≤2*10^6$

$60≤K≤200$

標籤:
dp fibonacci
出處:
[管理者:
frankie (34104)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」