D. 灯笼(lantern)

    传统题 文件IO:lantern 1000ms 256MiB

灯笼(lantern)

本题需要文件读写

文件 IO 为:输入文件 lantern.in,输出文件 lantern.out。请使用上述文件名读入和输出。

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

大蜀山开福寺始建于唐代,寺中每年新春会挂一串灯笼祈福。灯笼有两种颜色:金色(记为 G)和红色(记为 R)。灯笼的排列需要遵循一个规则:不允许出现两个连续的金色灯笼。

此外,还要求从左边数第 ⌊(n+1)/2⌋\lfloor(n+1)/2\rfloor 盏灯笼不能是金色。

现在要挂 nn 盏灯笼,请问有多少种合法的排列方式?

由于答案可能很大,请输出答案对 998244353998244353 取模后的结果。

⌊x⌋\lfloor x \rfloor 表示向下取整符号,即不超过 xx 的最大整数。

输入格式

输入仅包含一行,一个整数 nn。

输出格式

输出一行,一个整数,表示合法排列的数量对 998244353998244353 取模后的结果。

样例输入 1

3

样例输出 1

4

样例输入 2

4

样例输出 2

6

样例输入 3

5

样例输出 3

9

样例输入 4

6

样例输出 4

15

样例输入 5

7

样例输出 5

25

说明

样例解释

  • 样例 11 解释: n=3n=3,⌊(3+1)/2⌋=2\lfloor(3+1)/2\rfloor=2,即第 22 位不能为金色。 合法排列有:RRR、RRG、GRR、GRG,共 44 种。
  • 样例 22 解释: n=4n=4,⌊(4+1)/2⌋=2\lfloor(4+1)/2\rfloor=2,即第 22 位不能为金色。 不存在连续金色的合法排列共有 88 种,其中第 22 位为红色(合法)的有 66 种。
  • 样例 33 解释: n=5n=5,⌊(5+1)/2⌋=3\lfloor(5+1)/2\rfloor=3,即第 33 位不能为金色。 不存在连续金色的合法排列共有 1313 种,其中第 33 位为红色的有 99 种。
  • 样例 44 解释: n=6n=6,⌊(6+1)/2⌋=3\lfloor(6+1)/2\rfloor=3,即第 33 位不能为金色。 不存在连续金色的合法排列共有 2121 种,其中第 33 位为红色的有 1515 种。
  • 样例 55 解释: n=7n=7,⌊(7+1)/2⌋=4\lfloor(7+1)/2\rfloor=4,即第 44 位不能为金色。 不存在连续金色的合法排列共有 3434 种,其中第 44 位为红色的有 2525 种。

数据范围

对于所有测试数据,保证 3≤n≤1063 \le n \le 10^6。 保证所有的输入数值均为整数。

各测试点的附加限制如下表所示:

测试点编号 n≤n \le
1∼41 \sim 4 1010
5∼85 \sim 8 100100
9∼129 \sim 12 10001000
13∼1613 \sim 16 10510^5
17∼2017 \sim 20 10610^6
无金币奖励

2026合肥市蜀山区区赛小学组自测【民间数据】

未参加
状态
已结束
规则
IOI
题目
4
开始于
2026-10-19 22:15
结束于
2026-11-9 18:15
持续时间
500 小时
主持人
参赛人数
30