#PQJ233x4946. QOJ 233_4946
QOJ 233_4946
第一试青蕈领主(green) IOI 2018 中国国家队选拔赛暨精英赛 青蕈领主(green) 【题目背景】 ‘‘也许,我的生命也已经如同风中残烛了吧。’’ 小绿如是说。 【题目描述】 小绿同学因为微积分这门课,对‘‘连续’’ 这一概念产生了浓厚的兴趣。小绿打算把 连续的概念放到由整数构成的序列上,他定义一个长度为m 的整数序列是连续的,当 且仅当这个序列中的最大值与最小值的差,不超过m −1。例如{1, 3, 2} 是连续的,而 {1, 3} 不是连续的。 某天,小绿的顶头上司板老大,给了小绿T 个长度为n 的排列。小绿拿到之后十 分欢喜,他求出了每个排列的每个区间是否是他所定义的‘‘连续’’ 的。然而,小绿觉得 被别的‘‘连续’’ 区间包含住的‘‘连续’’ 区间不够优秀,于是对于每个排列的所有右端点 相同的‘‘连续’’ 区间,他只记录下了长度最长的那个‘‘连续’’ 区间的长度。也就是说, 对于板老大给他的每一个排列,他都只记录下了在这个排列中,对于每一个1 ≤i ≤n, 右端点为i 的最长‘‘连续’’ 区间的长度Li。显然这个长度最少为1,因为所有长度为1 的整数序列都是连续的。 做完这一切后,小绿爬上绿色床,美美地做了一个绿色的梦。 可是第二天醒来之后,小绿惊讶的发现板老大给他的所有排列都不见了,只剩下他 记录下来的T 组信息。小绿知道自己在劫难逃,但是作为一个好奇的青年,他还是想 知道:对于每一组信息,有多少个和信息符合的长度为n 的排列。 由于小绿已经放弃治疗了,你只需要告诉他每一个答案对998244353 取模的结果。 我们并不保证一定存在至少一个符合信息的排列,因为小绿也是人,他也有可能 犯错。 【输入格式】 从文件green.in 中读入数据。 输入的第一行包含两个整数T, n,分别表示板老大给小绿的排列个数、以及每个排 列的长度。 接下来T 行,每行描述一组信息,包含n 个正整数,第i 组信息的从左往右第j 个整数Li,j 表示第i 个排列中右端点为第j 个数的最长‘‘连续’’ 区间的长度。 对于每一行,如果行内包含多个数,则用单个空格将它们隔开。 【输出格式】 输出到文件green.out 中。 第10 页 共11 页 第一试青蕈领主(green) IOI 2018 中国国家队选拔赛暨精英赛 对于每组信息,输出一行一个整数表示可能的排列个数对998244353 取模的结果。 由于是计算机帮你算,所以我们不给你犯错的机会。 【样例1 输入】 1 3 1 1 3 【样例1 输出】 2 【样例2】 见选手目录下的green/green2.in 与green/green2.ans。 【样例3】 见选手目录下的green/green3.in 与green/green3.ans。 【子任务】 测试点编号 特殊性质 n ≤ T ≤ 1 ∼2 10 1 无 3 ∼4 10 100 5 Li,j = j 1 Li,j = 1 且j < n 6 300 无 7 ∼8 100 Li,j = 1 且j < n 9 1 1000 10 ∼12 无 13 ∼16 5000 100 17 ∼20 50, 000 对于所有测试数据,1 ≤T ≤100,1 ≤N ≤50000, 1 ≤Li,j ≤j。 【提示】 本题部分测试点的输入规模较大,请注意读入效率。 第11 页 共11 页