灯笼(lantern)
本题需要文件读写
文件 IO 为:输入文件
lantern.in,输出文件lantern.out。请使用上述文件名读入和输出。
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目描述
大蜀山开福寺始建于唐代,寺中每年新春会挂一串灯笼祈福。灯笼有两种颜色:金色(记为 G)和红色(记为 R)。灯笼的排列需要遵循一个规则:不允许出现两个连续的金色灯笼。
此外,还要求从左边数第 盏灯笼不能是金色。
现在要挂 盏灯笼,请问有多少种合法的排列方式?
由于答案可能很大,请输出答案对 取模后的结果。
表示向下取整符号,即不超过 的最大整数。
输入格式
输入仅包含一行,一个整数 。
输出格式
输出一行,一个整数,表示合法排列的数量对 取模后的结果。
样例输入 1
3
样例输出 1
4
样例输入 2
4
样例输出 2
6
样例输入 3
5
样例输出 3
9
样例输入 4
6
样例输出 4
15
样例输入 5
7
样例输出 5
25
说明
样例解释
- 样例 解释:
,,即第 位不能为金色。
合法排列有:
RRR、RRG、GRR、GRG,共 种。 - 样例 解释: ,,即第 位不能为金色。 不存在连续金色的合法排列共有 种,其中第 位为红色(合法)的有 种。
- 样例 解释: ,,即第 位不能为金色。 不存在连续金色的合法排列共有 种,其中第 位为红色的有 种。
- 样例 解释: ,,即第 位不能为金色。 不存在连续金色的合法排列共有 种,其中第 位为红色的有 种。
- 样例 解释: ,,即第 位不能为金色。 不存在连续金色的合法排列共有 种,其中第 位为红色的有 种。
数据范围
对于所有测试数据,保证 。 保证所有的输入数值均为整数。
各测试点的附加限制如下表所示:
| 测试点编号 | |
|---|---|
无金币奖励
2026合肥市蜀山区区赛小学组自测【民间数据】
- 状态
- 已结束
- 规则
- IOI
- 题目
- 4
- 开始于
- 2026-10-19 22:15
- 结束于
- 2026-11-9 18:15
- 持续时间
- 500 小时
- 主持人
- 参赛人数
- 30