{"problem":{"name":"[COCI 2023/2024 #5] Piratski kod","description":{"content":"Marrrtina 船长和她的海盗团队，在搜索了三个月之后，终于挖掘出一箱属于最著名的意大利海盗的失落宝藏。但是，要打开这个宝箱，她需要一个密码，该密码被描述在宝箱旁边的一个瓶子中的一条信息中。 信息如下： --- 只有最有价值的海盗才能打开宝箱，密码是以下谜题的答案：对于长度为 $a$ 的二进制序列 $s$，且其中唯一的连续两个 $1$ 位于序列的末尾，如果满足以下条件，它是一个数字 $x","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10259"},"statements":[{"statement_type":"Markdown","content":"Marrrtina 船长和她的海盗团队，在搜索了三个月之后，终于挖掘出一箱属于最著名的意大利海盗的失落宝藏。但是，要打开这个宝箱，她需要一个密码，该密码被描述在宝箱旁边的一个瓶子中的一条信息中。\n\n信息如下：\n\n---\n\n只有最有价值的海盗才能打开宝箱，密码是以下谜题的答案：对于长度为 $a$ 的二进制序列 $s$，且其中唯一的连续两个 $1$ 位于序列的末尾，如果满足以下条件，它是一个数字 $x$​ 的海盗表示：\n$$\ns[0]\\cdot \\text{Fib}[2] + s[1]\\cdot \\text{Fib}[3] + s[2]\\cdot \\text{Fib}[4] + \\ldots + s[a − 2]\\cdot \\text{Fib}[a] = \\sum_{i=0}^{a-2} s[i]\\cdot \\text{Fib}[2 + i] = x\n$$\n这里的 $\\text{Fib}[x]$ 表示第 $x$ 个斐波那契数。斐波那契数的定义如下：$\\text{Fib}[1] = 1$，$\\text{Fib}[2] = 1$，对于每个 $y > 2$，$\\text{Fib}[y] = \\text{Fib}[y − 1] + \\text{Fib}[y − 2]$。\n\n例如，$11_p = 1$，$011_p = 2$，$1010011_p = 17$，这里的 $p$ 表示数字的海盗表示。\n\n海盗代码是一个二进制序列（没有关于连续 $1$ 的任何条件），代表一系列正整数的序列。为了阅读它，我们将其分割为尽可能多的部分，这些部分是某些数字的海盗表示（可能还有一个不是任何数字的海盗表示的后缀），并按顺序写出这些整数。例如，我们将 $01111010110101$ 分割为 $011|11|01011|0101$，最后一部分不是海盗表示，因此我们删除它，得到 $011|11|01011$，并读到序列 $2,1,7$。\n\n海盗代码的值等于解码后的正整数序列的值之和。前面的密码的值为 $10$。\n\n我最喜欢的数字 $P$ 是长度为 $k$ 的所有海盗代码值的总和。由于该数字可能很大，打开宝箱的密码是 $P$ 除以 $10^9 + 7$ 的余数。\n\n— *Leonarrrdo da Pisa*\n\n---\n\n如果 Marrrtina 无法打开宝箱，她的船员将认为她不值得信任，并将她逼上走板。\n\n## Input\n\n一行一个整数 $n\\ (n\\le 5\\ 000)$。\n\n## Output\n\n输出一行 $n$ 个整数，其中第 $k$ 个整数表示长度为 $k$ 的密码谜题的答案。\n\n[samples]\n\n## Background\n\n**译自 [COCI 2023/2024 Contest #5](https://hsin.hr/coci/archive/2023_2024) T3「[Piratski kod](https://hsin.hr/coci/archive/2023_2024/contest5_tasks.pdf)」**\n\n## Note\n\n### 样例解释 1\n\n长度为 $1$ 的代码是 $0$ 和 $1$，它们的值都是 $0$。\n\n代码 $11$ 的值为 $1$，其余所有长度为 $2$ 的代码值都是 $0$。\n\n代码 $1111$ 的值为 $2$，$0011$ 的值为 $3$。\n\n### 子任务\n\n| Subtask | Points | Constraints |\n| :--: | :--: | :--: |\n| 1 | 20 | $n=20$ |\n| 2 | 40 | $n=300$ |\n| 3 | 50 | $n=5000$ |","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10259","tags":["动态规划 DP","2023","组合数学","COCI（克罗地亚）"],"sample_group":[["4\n","0 1 4 16\n"]],"created_at":"2026-03-03 11:09:25"}}