#SLT06D. 2026年S组模拟赛10连测第6场-T4 程老师的限量铺砖

2026年S组模拟赛10连测第6场-T4 程老师的限量铺砖

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

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

题目描述

程老师负责的一段走廊要重新铺地面。这段走廊的地面是一条笔直的长条,被划分成 nn 个 1×11\times 1 的格子,格子沿走廊方向依次排列。这一次要求把这 nn 个格子全部盖住:不留空缺,也不允许两块砖压到同一个格子上。

料房里备有两种规格的地砖,一种占 1×11\times 1 个格子,一种占 1×21\times 2 个格子。走廊只有这一行地面,所以大号砖只能顺着走廊方向摆放,也就是横放在相邻的两个格子上;地砖不旋转、不跨行、不切割。同一种规格的地砖彼此不做区分:两块同规格的砖互换位置不算新的铺法;反过来,只要存在某一个格子被不同规格的地砖盖住,两种铺法就算作不同的铺法。

领料台账上记着当天的存量:1×11\times 1 的砖至多领用 aa 块,1×21\times 2 的砖至多领用 bb 块,两种砖都不要求领满,剩下的退回料房。

请你统计在存量允许的范围内共有多少种铺法能把这段走廊铺满;如果存量范围内怎么排都铺不满,输出 00。由于铺法总数可能很大,输出它对 998244353998244353 取模的结果。

输入格式

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

输入共一行,包含三个整数 n,a,bn, a, b,含义如题目描述所述。

输出格式

输出到文件 tilep.out 中。

输出一行一个整数,表示能把走廊铺满的铺法总数对 998244353998244353 取模的结果。

样例

4 2 2
4

样例 1 解释

走廊有 44 个格子,料房里 1×11\times 1 的砖剩 22 块,1×21\times 2 的砖剩 22 块。把一种铺法按从左到右的顺序写成每块砖的规格序列(1 表示一块 1×11\times 1 砖,2 表示一块 1×21\times 2 砖)。先不管存量,能把 44 个格子盖满的写法有 55 条:1 1 1 1、1 1 2、1 2 1、2 1 1、2 2。再拿存量逐条核对:1 1 1 1 要用 44 块 1×11\times 1 砖,超出剩下的 22 块,这条作废;1 1 2、1 2 1、2 1 1 各用 22 块 1×11\times 1 砖和 11 块 1×21\times 2 砖,2 2 用 22 块 1×21\times 2 砖、一块 1×11\times 1 砖都不用,这 44 条都在存量之内。所以可用的铺法共 44 种。

5 5 5
8

样例 2 解释

走廊长 55,两种砖各剩 55 块,都不少于走廊的格子数,因此任何写法都不会超出存量。把 55 个格子盖满的写法共 88 条: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,每条用到的两种砖各自都不超过 55 块,所以这 88 条全部可用。

3 0 1
0

样例 3 解释

走廊有 33 个格子,料房里一块 1×11\times 1 砖都没有,1×21\times 2 砖只剩 11 块。若那块 1×21\times 2 砖不用,33 个格子都要靠 1×11\times 1 砖去补,可用的砖是 00 块;若用上那块 1×21\times 2 砖,它只占相邻的 22 个格子,剩下的 11 个格子仍然要由 1×11\times 1 砖去补,同样补不出来。两种情形都排不出完整的铺法,答案为 00。

数据范围

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

  • 1≤n≤1041 \le n \le 10^4;
  • 0≤a≤n0 \le a \le n,0≤b≤n0 \le b \le n。

各测试点的约束如下:

测试点 nn 特殊性质
1∼21\sim 2 ≤10\le 10 无
3∼63\sim 6 ≤20\le 20
7∼107\sim 10 ≤500\le 500
11∼1411\sim 14 ≤2000\le 2000
15∼1815\sim 18 ≤104\le 10^4
1919 A
2020 B
  • 特殊性质 A:a≥na \ge n 且 b≥nb \ge n。
  • 特殊性质 B:a=ba = b。
难度 未评定
通过率 —
尝试 0
通过 0
ID
3792
类型
传统题
Time Limit
1000ms
Memory Limit
512MiB
上传者