a230. OREREOOREOREREOREO - 旦旦解題農場

內容

某個悠閒的假日下午，迪西正愜意的滑著Instagram，看到了一張很有趣的圖

看完這張圖後，發現自己已經很久沒吃OREO了，迪西很想嘗試看看堆出OREREOOREOREREOREO，並把它吃掉，但他並不想吃掉REREREREREREO這種內餡連續超過2層或是頂層跟底層不是餅乾的鬼東西

現在有層數為n的內餡與餅乾的組合，請找出所有迪西能接受的組合總數

因為答案數可能過大請取100000007的餘數

OREOO OOREO 是不同的組合

假設輸入為4 可能有 OOOO OREOO OOREO OREREO 共4種方法所以就輸出4

輸入說明

輸入一行層數n

一個測資點至多5筆測資

保證所有 $n \geq 3$

#00 $n \leq 10^1$

#01 $n \leq 10^2$

#02 $n \leq 10^3$

#03 $n \leq 10^4$

#04 $n \leq 10^5$

#05 $n \leq 10^6$

#06 $n \leq 10^7$

輸出說明

輸出所有的可能數

記得取100000007的餘數

範例輸入

範例輸出

測資資訊：

記憶體限制： 128 MB
公開測資點#0 (10%): 1.0s , <1K
公開測資點#1 (10%): 1.0s , <1K
公開測資點#2 (10%): 1.0s , <1K
公開測資點#3 (10%): 1.0s , <1K
公開測資點#4 (10%): 1.0s , <1K
公開測資點#5 (10%): 1.0s , <1K
公開測資點#6 (40%): 1.0s , <1K

提示：

$Dynamic Programming$

標籤:

出處:

[管理者：

fdhs108_38002 (NULL)

]

編號	身分	題目	主題	人氣	發表日期
4779	aaaron08813 (12th 副初階教學/柏霖)	a230	$mod$	141	2023-08-05 23:42