【UR #26】石子合并 - 题目 - Universal Online Judge

在藏蓝铁路的碧水湖大桥落成之际，一群铁路工程蚤聚在一起，庆祝这一伟大的建筑工程。

他们在桥上放置了代表各个工程团队的 $n$ 个石堆，每一个石堆代表了一个工程团队带来的材料和设备。

根据工程蚤 M 蚤的说法，他们为了保证碧水湖大桥的稳定性，特意研制了一种名为「跳蚤搭堆法」的搭建材料方法。为了体现这种方法的优越性，每个石堆由至少一个石子按顺序排布再根据「跳蚤搭堆法」依次搭建形成，相当于可以用一个非空有序列表描述，石子的数量代表了该团队所贡献的资源数量。每个石子还根据其大小分配了一个不大于 $m$ 的正整数编号，象征着这份资源对大桥工程所带来的贡献大小。不同石子之间的编号可能相同。对于两个编号相同的石子，我们认为它们是相同的。

为了纪念这一时刻，工程蚤们决定将这些石堆合并成一个大石堆，从而来构建一个代表团结和合作的雕塑。

由于「跳蚤搭堆法」的特性，合并两个石堆 $A$ 和 $B$ 的过程可以用如下 C++ 代码表示：

#define stone int
#define stones std::vector<stone>
stones merge(stones A, stones B)
{
    stones C;
    while (A.size() && B.size())
        if (A[0] <= B[0])
            C.push_back(A[0]), A.erase(A.begin());
        else
            C.push_back(B[0]), B.erase(B.begin());
    while(A.size())
        C.push_back(A[0]), A.erase(A.begin());
    while(B.size())
        C.push_back(B[0]), B.erase(B.begin());
    return C;
}

返回的石堆就是最终搭建的结果。

作为睿智的数学家伏特，你当然看出来这就是所谓的「二路归并算法」，只是石堆内部的石子不一定有序。

工程蚤们首先选择了一个基础的石堆 $A_{1}$ ，然后依次选择其他的石堆与其合并。

合并的规则如下：对于 $i = 2, 3, \dots, n$ ，他们选择石堆 $A_{1}$ 与 $A_{i}$ 合并，形成一个新的大石堆，作为新的石堆 $A_{1}$ 。

完成所有合并后，他们惊奇地发现： $A_{1}$ 的大小恰好为 $m$ ！而里面的石头编号依次为 $a_{1}, a_{2}, \dots, a_{m}$ 。

这个时候跳蚤国王来了，他看到这个雕塑非常满意。他问道：“在开始的时候，这些石堆是怎样的呢？”

他想知道，给定合并后的石堆，有多少种可能的初始石堆 $A_{1}, A_{2}, \dots, A_{n}$ 组合可以得到这样的结果。

作为杰出的数学家伏特，你能帮助跳蚤国王解决这个问题吗？

你需要计算有多少种可能的初始石堆形态，并输出答案模 $998244353$ 后的值。由于可能搭建过程难免会产生失误，可能会没有合法方案，如果这样请输出 $0$ 。

简要题意

目前有 $n$ 个非空数组 $A_{1}, A_{2}, \dots, A_{n}$ （每个数组内部不一定有序），其元素均在 $[1, m]$ 之间。

对 $i = 2, 3, \dots, n$ 依次执行 $A_{1} \leftarrow merge (A_{1}, A_{i})$ 后， $A_{1}$ 大小恰为 $m$ ，且 $A_{1}$ 中的元素依次为 $a_{1}, a_{2}, \dots a_{m}$ 。

现给定 $a_{1}, a_{2}, \dots, a_{m}$ ，问有多少种可能的初始数组 $A_{1}, A_{2}, \dots, A_{n}$ ，对 $998244353$ 取模。

无解时请输出 $0$ 。

输入格式

第一行三个整数 $n, m, o$ ，其中 $o$ 表示该测试点的一些特殊性质（请参见「数据范围」一节的描述）。

接下来一行 $m$ 个整数，依次为 $a_{1}, a_{2}, \dots a_{m}$ 。

输出格式

一行一个整数，表示方案数对 $998244353$ 取模后的结果。

样例一

input

3 8 0
1 3 4 2 5 2 7 8

output

样例二

input

4 8 0
2 4 1 4 1 2 3 2

output

样例三 $\sim$ 样例二十

见附件下载。

M 蚤的小提示

为了方便非 C++ 选手的理解，善良的 M 蚤给了你在「跳蚤搭堆法」下合并两个石堆的一份伪代码：

$\begin{aligned} f u n c t i o n merge (s t o n e s A, s t o n e s B) \\ s t o n e s C \leftarrow \emptyset \\ w h i l e A \neq \emptyset \land B \neq \emptyset \\ x \leftarrow the first stone of A \\ y \leftarrow the first stone of B \\ i f x \leq y \\ C push back x \\ pop the front of A \\ e l s e \\ C push back y \\ pop the front of B \\ f i \\ e n d w h i l e \\ w h i l e A \neq \emptyset \\ x \leftarrow the first stone of A \\ C push back x \\ pop the front of A \\ e n d w h i l e \\ w h i l e B \neq \emptyset \\ x \leftarrow the first stone of B \\ C push back x \\ pop the front of B \\ e n d w h i l e \\ r e t u r n C \\ e n d f u n c t i o n \end{aligned}$

数据范围

所有数据保证 $2 \leq n \leq 2 \times 10^{5}$ ， $n \leq m \leq 5 \times 10^{5}$ ， $1 \leq a_{i} \leq m$ ， $0 \leq o \leq 5$ 。

具体的数据规模分布可以见下表。 $o$ 为指示特殊性质的参数，其含义将在之后注明。

子任务编号	$n$	$m$	$o$	分值	子任务依赖
$1$	$\leq 4$	$\leq 8$	$= 0$	$5$	无
$2$	$= 2$	$\leq 20$	$= 0$	$5$	无
$3$	$\leq 100$	$\leq 300$	$= 1$	$10$	无
$4$	$\leq 100$	$\leq 300$	$= 0$	$10$	$1, 2, 3$
$5$	$\leq 1000$	$\leq 3000$	$= 1$	$10$	$3$
$6$	$\leq 1000$	$\leq 3000$	$= 0$	$10$	$4, 5$
$7$	$\leq 2 \times 10^{5}$	$\leq 5 \times 10^{5}$	$= 5$	$10$	无
$8$	$\leq 2 \times 10^{5}$	$\leq 5 \times 10^{5}$	$= 4$	$5$	$7$
$9$	$\leq 2 \times 10^{5}$	$\leq 5 \times 10^{5}$	$= 3$	$10$	无
$10$	$\leq 2 \times 10^{5}$	$\leq 5 \times 10^{5}$	$= 2$	$5$	$1, 2, 9$
$11$	$\leq 2 \times 10^{5}$	$\leq 5 \times 10^{5}$	$= 1$	$10$	$5, 7, 9$
$12$	$\leq 2 \times 10^{5}$	$\leq 5 \times 10^{5}$	$= 0$	$10$	$6, 8, 10, 11$

接下来阐述关于 $o$ 的特殊性质。

当 $o \in {1, 3, 5}$ 时，保证 $\forall 1 \leq i < m, a_{i} \leq a_{i + 1}$ 。
当 $2 \leq o \leq 3$ 时，保证 $\forall 1 \leq i < m, a_{i} \leq 20$ 。
当 $4 \leq o \leq 5$ 时，保证每种编号出现次数均不超过 $5$ 次。

时间限制： $2 s$

空间限制： $1 GB$

Universal Online Judge

UOJ

UOJ Round #26

A. 石子合并

简要题意

输入格式

输出格式

样例一

input

output

样例二

input

output

样例三 $\sim$ 样例二十

M 蚤的小提示

数据范围

Universal Online Judge

UOJ

UOJ Round #26

A. 石子合并

简要题意

输入格式

输出格式

样例一

input

output

样例二

input

output

样例三 ∼$\sim$ 样例二十

M 蚤的小提示

数据范围

样例三 $\sim$ 样例二十