#SLT06D. 2026年S组模拟赛10连测第6场-T4 程老师的限量铺砖
2026年S组模拟赛10连测第6场-T4 程老师的限量铺砖
| 项目 | 内容 |
|---|---|
| 输入文件名 | tilep.in |
| 输出文件名 | tilep.out |
| 可执行文件名 | tilep |
| 每个测试点时限 | 1.0 秒 |
| 内存限制 | 512 MiB |
| 测试点数目 | 20 |
| 是否等分 | 是 |
结果比较方式为全文比较(过滤行末空格及文末换行)。
题目描述
程老师负责的一段走廊要重新铺地面。这段走廊的地面是一条笔直的长条,被划分成 个 的格子,格子沿走廊方向依次排列。这一次要求把这 个格子全部盖住:不留空缺,也不允许两块砖压到同一个格子上。
料房里备有两种规格的地砖,一种占 个格子,一种占 个格子。走廊只有这一行地面,所以大号砖只能顺着走廊方向摆放,也就是横放在相邻的两个格子上;地砖不旋转、不跨行、不切割。同一种规格的地砖彼此不做区分:两块同规格的砖互换位置不算新的铺法;反过来,只要存在某一个格子被不同规格的地砖盖住,两种铺法就算作不同的铺法。
领料台账上记着当天的存量: 的砖至多领用 块, 的砖至多领用 块,两种砖都不要求领满,剩下的退回料房。
请你统计在存量允许的范围内共有多少种铺法能把这段走廊铺满;如果存量范围内怎么排都铺不满,输出 。由于铺法总数可能很大,输出它对 取模的结果。
输入格式
从文件 tilep.in 中读入数据。
输入共一行,包含三个整数 ,含义如题目描述所述。
输出格式
输出到文件 tilep.out 中。
输出一行一个整数,表示能把走廊铺满的铺法总数对 取模的结果。
样例
4 2 2
4
样例 1 解释
走廊有 个格子,料房里 的砖剩 块, 的砖剩 块。把一种铺法按从左到右的顺序写成每块砖的规格序列(1 表示一块 砖,2 表示一块 砖)。先不管存量,能把 个格子盖满的写法有 条:1 1 1 1、1 1 2、1 2 1、2 1 1、2 2。再拿存量逐条核对:1 1 1 1 要用 块 砖,超出剩下的 块,这条作废;1 1 2、1 2 1、2 1 1 各用 块 砖和 块 砖,2 2 用 块 砖、一块 砖都不用,这 条都在存量之内。所以可用的铺法共 种。
5 5 5
8
样例 2 解释
走廊长 ,两种砖各剩 块,都不少于走廊的格子数,因此任何写法都不会超出存量。把 个格子盖满的写法共 条:1 1 1 1 1、1 1 1 2、1 1 2 1、1 2 1 1、2 1 1 1、1 2 2、2 1 2、2 2 1,每条用到的两种砖各自都不超过 块,所以这 条全部可用。
3 0 1
0
样例 3 解释
走廊有 个格子,料房里一块 砖都没有, 砖只剩 块。若那块 砖不用, 个格子都要靠 砖去补,可用的砖是 块;若用上那块 砖,它只占相邻的 个格子,剩下的 个格子仍然要由 砖去补,同样补不出来。两种情形都排不出完整的铺法,答案为 。
数据范围
对于所有测试数据,保证:
- ;
- ,。
各测试点的约束如下:
| 测试点 | 特殊性质 | |
|---|---|---|
| 无 | ||
| A | ||
| B |
- 特殊性质 A: 且 。
- 特殊性质 B:。
- ID
- 3792
- 类型
- 传统题
- Time Limit
- 1000ms
- Memory Limit
- 512MiB
- 上传者