#SLT02C. 2026年S组模拟赛10连测第2场-T3 合影排位

2026年S组模拟赛10连测第2场-T3 合影排位

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

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

题目描述

毕业季,年级组织各班拍摄合影。某班共有 nn 位同学,平日按座次编号为 11 到 nn;合影场地划出一排 nn 个位置,同样编号为 11 到 nn。

班委排队时沿用平日的座次习惯:编号为 ii 的同学只能站在编号 与 ii 相距不超过 kk 的位置上,即站位 xx 须满足 ∣x−i∣≤k|x - i| \le k 且 1≤x≤n1 \le x \le n。排定后,每个位置 恰好站一位同学(因此每位同学也恰好占据一个位置)。

一种排队方案由每个位置上所站同学的编号唯一确定;两种方案只要存在一个位置上所站同学不同,就视为不同的方案。请计算满足上述习惯的排队方案总数。由于总数可能很大,只需输出它对 998244353998244353 取模的结果。

输入格式

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

一行两个整数 n,kn, k。

输出格式

输出到文件 lineup.out 中。

输出一行一个整数,表示排队方案总数对 998244353998244353 取模的结果。

样例

3 1
3

样例 1 解释

用 (a1,a2,a3)(a_1, a_2, a_3) 表示位置 1,2,31, 2, 3 上依次所站同学的编号。11 号只能站位置 11 或 22,33 号只能站位置 22 或 33。全部合法方案为 (1,2,3)(1, 2, 3)、(1,3,2)(1, 3, 2)、(2,1,3)(2, 1, 3),共 33 种。

5 1
8

样例 2 解释

全部合法方案为 (1,2,3,4,5)(1, 2, 3, 4, 5)、(1,2,3,5,4)(1, 2, 3, 5, 4)、(1,2,4,3,5)(1, 2, 4, 3, 5)、(1,3,2,4,5)(1, 3, 2, 4, 5)、(1,3,2,5,4)(1, 3, 2, 5, 4)、(2,1,3,4,5)(2, 1, 3, 4, 5)、(2,1,3,5,4)(2, 1, 3, 5, 4)、(2,1,4,3,5)(2, 1, 4, 3, 5),共 88 种。

6 2
73

样例 3 解释

按位置 11 所站的同学分类计数:站 11 号时,其余五个位置共 3131 种排法;站 22 号时共 2424 种;站 33 号时共 1818 种。合计 31+24+18=7331 + 24 + 18 = 73 种。

数据范围

对于所有测试数据,保证:1≤n≤1051 \le n \le 10^5,0≤k≤40 \le k \le 4。

各测试点的约束如下:

测试点 nn kk 特殊性质
1∼31\sim3 ≤10\le 10 ≤4\le 4 无
4∼84\sim8 ≤20\le 20
9∼139\sim13 ≤105\le 10^5 ≤1\le 1
14∼2014\sim20 ≤4\le 4
难度 未评定
通过率 —
尝试 0
通过 0
ID
3775
类型
传统题
Time Limit
1000ms
Memory Limit
512MiB
上传者