#SLT09B. 2026年S组模拟赛10连测第9场-T2 程老师的灯串编程
2026年S组模拟赛10连测第9场-T2 程老师的灯串编程
| 项目 | 内容 |
|---|---|
| 输入文件名 | lightstr.in |
| 输出文件名 | lightstr.out |
| 可执行文件名 | lightstr |
| 每个测试点时限 | 1.0 秒 |
| 内存限制 | 512 MiB |
| 测试点数目 | 20 |
| 是否等分 | 是 |
结果比较方式为全文比较(过滤行末空格及文末换行)。
题目描述
程老师在调试一批灯串的控制程序。每条灯串上从左到右依次排开 个灯位,每个灯位要么点亮,要么熄灭。把点亮的灯位记作 1,熄灭的灯位记作 0,那么给一条灯串编程的结果就是一段长度 的 0/1 串;两个填法只要某一个灯位上的取值不同,就当作不同的填法。
这批灯串的线路有两条既定的规矩。第一条是供电规矩:灯串上任意连续 3 个灯位中,点亮的灯位至多 2 个——三盏相邻的灯位同时点亮会超出这一段线路的承载。第二条是编排规矩:一段填法所对应的整条灯串上,点亮的灯位个数恰好为 个。
一段填法必须同时满足这两条规矩。对给定的 和 ,程老师想知道一共有多少种不同的填法能够同时满足它们。由于数目可能很大,请给出这个数目对 取模后的结果。
输入格式
从文件 lightstr.in 中读入数据。
一行两个整数 。
输出格式
输出到文件 lightstr.out 中。
一行一个整数,表示同时满足两条规矩的填法数对 取模后的结果。
样例
3 2
3
样例 1 解释
三个灯位里要点亮两盏。三盏灯全亮的那种填法把连续三个灯位都点上了,违反供电规矩,先排除掉。剩下的填法有 110、101、011,它们都只点亮两盏,任意连续三个灯位里点亮的灯都不超过两个,供电规矩不会拒绝其中任何一种。因此共有 种填法。
4 2
6
样例 2 解释
四个灯位里要点亮两盏,把两盏亮灯所在的位置逐一看下来,能写出的填法是 0011、0101、0110、1001、1010、1100。这些填法各自都只有两盏灯亮着,无论怎么取连续三个灯位,里面的亮灯都不会超过两个,供电规矩对它们都不作限制,全部保留。因此共有 种填法。
数据范围
对于所有测试数据,保证:
- ,。
各测试点的约束如下:
| 测试点 | 特殊性质 | |
|---|---|---|
| 无 | ||
| A | ||
| B |
- 特殊性质 A:。
- 特殊性质 B:。
难度
未评定
通过率
—
尝试
0
通过
0
- ID
- 3802
- 类型
- 传统题
- Time Limit
- 1000ms
- Memory Limit
- 512MiB
- 上传者