UOJ Logo Universal Online Judge

UOJ

#821. 【UR #26】石子合并

附件下载 统计

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

他们在桥上放置了代表各个工程团队的 $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\textrm{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

540

样例二

input

4 8 0
2 4 1 4 1 2 3 2

output

0

样例三 $\sim$ 样例二十

见附件下载。

M 蚤的小提示

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

$ \begin{aligned} &\mathop{\bf function}\textrm{merge}(\mathop{\bf stones}A,\mathop{\bf stones}B)\\ &\quad\mathop{\bf stones}C\leftarrow\varnothing\\ &\quad\mathop{\bf while}A\neq\varnothing\land B\neq\varnothing\\ &\quad\quad x\leftarrow\textrm{the first stone of }A\\ &\quad\quad y\leftarrow\textrm{the first stone of }B\\ &\quad\quad\mathop{\bf if}x\le y\\ &\quad\quad\quad C\textrm{ push back }x\\ &\quad\quad\quad\textrm{pop the front of }A\\ &\quad\quad\mathop{\bf else}\\ &\quad\quad\quad C\textrm{ push back }y\\ &\quad\quad\quad\textrm{pop the front of }B\\ &\quad\quad\mathop{\bf fi}\\ &\quad\mathop{\bf end}\mathop{\bf while}\\ &\quad\mathop{\bf while}A\neq\varnothing\\ &\quad\quad x\leftarrow\textrm{the first stone of }A\\ &\quad\quad C\textrm{ push back }x\\ &\quad\quad\textrm{pop the front of }A\\ &\quad\mathop{\bf end}\mathop{\bf while}\\ &\quad\mathop{\bf while}B\neq\varnothing\\ &\quad\quad x\leftarrow\textrm{the first stone of }B\\ &\quad\quad C\textrm{ push back }x\\ &\quad\quad\textrm{pop the front of }B\\ &\quad\mathop{\bf end}\mathop{\bf while}\\ &\quad\mathop{\bf return}C\\ &\mathop{\bf end}\mathop{\bf function} \end{aligned} $

数据范围

所有数据保证 $2\le n\le2\times10^5$,$n\le m\le5\times10^5$,$1\le a_i\le m$,$0\le o\le 5$。

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

子任务编号 $n$ $m$ $o$ 分值 子任务依赖
$1$ $\le4$ $\le8$ $=0$ $5$
$2$ $=2$ $\le20$ $=0$ $5$
$3$ $\le100$ $\le300$ $=1$ $10$
$4$ $\le100$ $\le300$ $=0$ $10$ $1,2,3$
$5$ $\le1000$ $\le3000$ $=1$ $10$ $3$
$6$ $\le1000$ $\le3000$ $=0$ $10$ $4,5$
$7$ $\le2\times10^5$ $\le5\times10^5$ $=5$ $10$
$8$ $\le2\times10^5$ $\le5\times10^5$ $=4$ $5$ $7$
$9$ $\le2\times10^5$ $\le5\times10^5$ $=3$ $10$
$10$ $\le2\times10^5$ $\le5\times10^5$ $=2$ $5$ $1,2,9$
$11$ $\le2\times10^5$ $\le5\times10^5$ $=1$ $10$ $5,7,9$
$12$ $\le2\times10^5$ $\le5\times10^5$ $=0$ $10$ $6,8,10,11$

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

  • 当 $o\in\{1,3,5\}$ 时,保证 $\forall1\le i< m,a_i\le a_{i+1}$。
  • 当 $2\le o\le3$ 时,保证 $\forall1\le i< m,a_i\le20$。
  • 当 $4\le o\le5$ 时,保证每种编号出现次数均不超过 $5$ 次。

时间限制:$2\texttt{s}$

空间限制:$1\texttt{GB}$