排組鴨

發布時間: July 8, 2024, 4:52 p.m.   最後更新時間: July 8, 2024, 5:05 p.m.   時間限制: 1000ms   記憶體限制: 128M

「上一題被你投雞取巧的解出來了是嗎?」hush心有不甘的說到「但是這題可是我的鴨箱寶!不會輕易放過你的」

鴨,俗稱鴨子,是對鴨科部分「屬」中的鳥類的通用名稱,其餘同屬鴨科但不稱作鴨的有天鵝、鵝、雁及鴛鴦等。鴨均為游禽,通常體形比天鵝和鵝小,人們在淡水和鹹水都可以看見它們的身影。 (by Wikipedia)

duck.png

.

.

.

挑戰書如下:

在鴨抑了許久過後,hush決定要連續好幾天每天都吃一隻鴨,以達到「鴨咧鴨咧」的境界。已知有些鴨子因為長期被人為飼養的關係,所以數量穩定可以一直吃;反之有些鴨子是保育類的,所以只能吃一次就不能再吃了。(lll¬ω¬)

(這段增加了不少難度QwQ qwq) 而且hush發現自己很怕無聊,連續太多天吃同一種鴨子會嚴重影響它身心健康,害他長不高\(〇_o)/
,因此他不能連續太多天吃同一種鴨子ㄏㄚˋㄏㄚˋㄏㄚˋ 。

給你hush要吃幾天鴨子、有幾種人為飼養和保育類的鴨子、不能連續超過幾天吃同一種鴨子, 你 能算出hush有幾種吃鴨子的可能性嗎?

給你$4$個整數$d,n,m,k$,分別代表hush要吃幾天鴨子,有幾種人為飼養的鴨子,有幾種保育類的鴨子,不能連續超過($\le$)幾天吃同一種鴨子
($1\le d\le 3\times 10^2, 0\le n\le 10^6, 0\le m\le 3\times 10^2, 1\le k\le 20$)

由於答案可能皮頁大,輸出答案對$999999937$取餘

複製範例
3 4 2 2
180
複製範例
300 100000000 300 20
201916985

把樹狀圖簡化成函數,就像段考那樣

以下也是AC之後在看:

「什麼!我竟然又敗在你手裡了,但你以為雞鴨出完了我就想不到其他動物了嗎?」hush露出一抹詭異的微笑。*^____^*「別忘了,還有⨉⨉⨉可以出呢!」

dp

hush