給定正整數 $n$
請問有多少種長度為 $n$ 的 01 字串不包含 1+0+1+0+ 及 0+1+0+1+ 格式的子字串？
(其中 + 表示前一字元重複 $1$ 次以上)
例如 11011 符合格式，而 00110111001 則不符合
因為 00110111001 包含了 01101，該子字串為 0+1+0+1+ 格式
給定正整數 $n$ ($1 \leq n \leq 10^9$)
輸出共有幾種長度為 $n$ 的 01 字串不包含 1+0+1+0+ 及 0+1+0+1+ 格式的子字串
0 或 1第二筆範例 00、01、10、11 皆符合格式
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0~6 | 100 |
| No. | Time Limit (ms) | Memory Limit (KiB) | Output Limit (KiB) | Subtasks |
|---|---|---|---|---|
| 0 | 100 | 65536 | 65536 | |
| 1 | 100 | 65536 | 65536 | |
| 2 | 100 | 65536 | 65536 | |
| 3 | 100 | 65536 | 65536 | |
| 4 | 100 | 65536 | 65536 | |
| 5 | 100 | 65536 | 65536 | |
| 6 | 100 | 65536 | 65536 |