#PQJ1930x10152. QOJ 1930_10152
QOJ 1930_10152
2025 联合省选 第二试封印(seal) 封印(seal) 【题目描述】 在一次探险中,小H 发现了一个古老的封印。封印的本体是一个长度为n 的序列 A = [a1, a2, . . . , an]。初始,每个元素都是1 至m 间的正整数。 设|A| 表示序列A 的长度,小H 可以对序列进行以下修改:
- 选择序列A 的某个.严.格前缀最大值元素as,即选择1 ≤s ≤|A| 满足∀1 ≤j < s, as > aj,特别地,a1 总是序列A 的严格前缀最大值;
- 若as̸ = 1,将(as −1) 插入序列A 的尾端;
- 删去序列A 的前s 个元素。 考虑如下例子:在A = [1, 3, 2, 3, 4] 时, • 小H 可以选择s = 1,此时修改后的序列为[3, 2, 3, 4]; • 小H 可以选择s = 2,此时修改后的序列为[2, 3, 4, 2]; • 小H 不能选择s = 4,因为a2 = a4 = 3,这意味着a4 并非严格前缀最大值。 小H 可以进行任意多次修改操作,也可以不进行任何修改。为了解开封印,小H 想知道:通过以上修改操作,他可以得到多少种不同的.非.空序列。 认为两个序列A = [a1, . . . , an] 和B = [b1, . . . , bm] 不同,当且仅当n̸ = m 或 ∃1 ≤i ≤min{n, m}, ai̸ = bi。 由于答案可能很大,你只需告诉小H 答案对998, 244, 353 取模后的结果。 【输入格式】 从文件seal.in 中读入数据。 .本.题.有.多.组.测.试.数.据。输入的第一行两个整数c, T,分别表示测试点编号和测试数 据组数,接下来输入每组测试数据。样例满足c = 0。 对于每组测试数据,第一行两个整数n, m,分别表示序列长度与值域,第二行n 个 整数a1, a2, . . . , an,描述序列A。 【输出格式】 输出到文件seal.out 中。 对于每组测试数据输出一行一个整数,表示通过修改操作可以得到的.非.空序列个 数,对998, 244, 353 取模。 【样例1 输入】 1 0 4 2 3 2 第8 页 共11 页
2025 联合省选 第二试封印(seal) 3 1 2 1 4 4 3 5 3 1 2 1 6 5 4 7 1 3 2 3 4 8 7 5 9 4 4 5 2 3 3 1 【样例1 输出】 1 4 2 7 3 20 4 59 【样例1 解释】 该组样例共有4 组测试数据。 • 对于第一组测试数据,可以通过修改得到的非空序列有[1, 2, 1], [2, 1], [1, 1], [1]。 • 对于第二组测试数据,可以通过修改操作得到的非空序列有[3, 1, 2, 1], [1, 2, 1, 2], [2, 1, 2], [1, 2, 1], [2, 1], [1, 1], [1]。 【样例2 输入】 1 0 2 2 11 10 3 8 8 8 9 9 8 8 9 9 9 8 4 12 2500 5 1529 1470 1361 1416 1492 1503 1641 1868 1829 1959 2052 2105 【样例2 输出】 1 694 2 4961744 第9 页 共11 页
2025 联合省选 第二试封印(seal) 【样例3】 见选手目录下的seal/seal3.in 与seal/seal3.ans。 该组样例满足测试点3 ∼5 的限制。 【样例4】 见选手目录下的seal/seal4.in 与seal/seal4.ans。 该组样例满足测试点10 的限制。 【样例5】 见选手目录下的seal/seal5.in 与seal/seal5.ans。 该组样例满足测试点11 ∼14 的限制。 【样例6】 见选手目录下的seal/seal6.in 与seal/seal6.ans。 该组样例满足测试点15 的限制。 【样例7】 见选手目录下的seal/seal7.in 与seal/seal7.ans。 该组样例满足测试点17 ∼19 的限制。 【样例8】 见选手目录下的seal/seal8.in 与seal/seal8.ans。 该组样例满足测试点22 ∼25 的限制。 【子任务】 对于所有测试点, • 1 ≤T ≤10, • 1 ≤n, m ≤2, 500, • ∀1 ≤i ≤n, 1 ≤ai ≤m。 第10 页 共11 页
2025 联合省选 第二试封印(seal) 测试点编号 n ≤ m ≤ 特殊性质 1, 2 10 10 无 3 ∼5 18 70 6 A 7, 8 AB 9 70 A 10 AB 11 ∼14 无 15 300 300 A 16 AB 17 ∼19 无 20 2,500 2,500 A 21 AB 22 ∼25 无 特殊性质A:∀1 ≤i < j ≤n, ai̸ = aj。 特殊性质B:∀1 ≤i < n, ai < ai+1。 第11 页 共11 页