#SLT09B. 2026年S组模拟赛10连测第9场-T2 程老师的灯串编程

2026年S组模拟赛10连测第9场-T2 程老师的灯串编程

项目 内容
输入文件名 lightstr.in
输出文件名 lightstr.out
可执行文件名 lightstr
每个测试点时限 1.0 秒
内存限制 512 MiB
测试点数目 20
是否等分 是

结果比较方式为全文比较(过滤行末空格及文末换行)。

题目描述

程老师在调试一批灯串的控制程序。每条灯串上从左到右依次排开 nn 个灯位,每个灯位要么点亮,要么熄灭。把点亮的灯位记作 1,熄灭的灯位记作 0,那么给一条灯串编程的结果就是一段长度 nn 的 0/1 串;两个填法只要某一个灯位上的取值不同,就当作不同的填法。

这批灯串的线路有两条既定的规矩。第一条是供电规矩:灯串上任意连续 3 个灯位中,点亮的灯位至多 2 个——三盏相邻的灯位同时点亮会超出这一段线路的承载。第二条是编排规矩:一段填法所对应的整条灯串上,点亮的灯位个数恰好为 jj 个。

一段填法必须同时满足这两条规矩。对给定的 nn 和 jj,程老师想知道一共有多少种不同的填法能够同时满足它们。由于数目可能很大,请给出这个数目对 998244353998244353 取模后的结果。

输入格式

从文件 lightstr.in 中读入数据。

一行两个整数 n,jn, j。

输出格式

输出到文件 lightstr.out 中。

一行一个整数,表示同时满足两条规矩的填法数对 998244353998244353 取模后的结果。

样例

3 2
3

样例 1 解释

三个灯位里要点亮两盏。三盏灯全亮的那种填法把连续三个灯位都点上了,违反供电规矩,先排除掉。剩下的填法有 110、101、011,它们都只点亮两盏,任意连续三个灯位里点亮的灯都不超过两个,供电规矩不会拒绝其中任何一种。因此共有 33 种填法。

4 2
6

样例 2 解释

四个灯位里要点亮两盏,把两盏亮灯所在的位置逐一看下来,能写出的填法是 0011、0101、0110、1001、1010、1100。这些填法各自都只有两盏灯亮着,无论怎么取连续三个灯位,里面的亮灯都不会超过两个,供电规矩对它们都不作限制,全部保留。因此共有 66 种填法。

数据范围

对于所有测试数据,保证:

  • 1≤n≤10001 \le n \le 1000,0≤j≤n0 \le j \le n。

各测试点的约束如下:

测试点 nn 特殊性质
1∼21\sim2 ≤10\le 10 无
3∼63\sim6 ≤20\le 20
7∼87\sim8 ≤22\le 22
9∼109\sim10 ≤200\le 200
11∼1411\sim14 ≤500\le 500
15∼1815\sim18 ≤1000\le 1000
1919 A
2020 B
  • 特殊性质 A:j=0j = 0。
  • 特殊性质 B:j≤2j \le 2。
难度 未评定
通过率 —
尝试 0
通过 0
ID
3802
类型
传统题
Time Limit
1000ms
Memory Limit
512MiB
上传者