UOJ Logo Universal Online Judge

UOJ

#585. 【ZJOI2020】传统艺能

附件下载 统计

Bob 喜欢线段树。

众所周知,ZJOI 的第二题有很多线段树。

Bob 有一棵根为 $[1, n]$ 的广义线段树。Bob 需要在这个线段树上执行 $k$ 次区间懒标记操作,每次操作会等概率地从 $[1, n]$ 的所有 $\frac{n(n+1)}2$ 个子区间中随机选择一个。对于所有在该次操作中被访问到的非叶子节点,Bob 会将这个点上的标记下推;而对于所有叶子节点(即没有继续递 归的节点),Bob 会给这个点打上标记。

Bob 想知道,$k$ 次操作之后,有标记的节点的期望数量是多少。

具体定义

线段树:线段树是一棵每个节点上都记录了一个线段的二叉树。根节点记录的线段是 $[1, n]$。

对于每个节点,若它记录的线段是 $[l, r]$ 且 $l\neq r$,取 $m = \lfloor \frac{l+r}2 \rfloor$,则它的左右儿子节点记录的线段分别是 $[l,m]$ 和 $[m + 1, r]$;若 $l = r$,则它是叶子节点。

广义线段树:在广义的线段树中,$m$ 不要求恰好等于区间的中点,但是 $m$ 还是必须满足 $l\le m < r$ 的。不难发现在广义的线段树中,树的深度可以达到 $O(n)$ 级别。

线段树的核心是懒标记,下面是一个带懒标记的广义线段树的伪代码,其中 tag 数组为懒标记:

伪代码

注意,在处理叶子节点时,一旦他获得了一个标记,那么这个标记会一直存在。

你也可以这么理解题意:有一棵广义线段树,每个节点有一个 $m$ 值。一开始 tag 数组均为 $0$,Bob 会执行 $k$ 次操作,每次操作等概率随机选择区间 $[l, r]$ 并执行 MODIFY(root, 1, n, l, r);

最后所有 Node 中满足 tag[Node] = 1 的期望数量就是需要求的值。

输入格式

第一行输入两个整数 $n, k$。

接下来输入一行包含 $n − 1$ 个整数 $a_i$:按照先序遍历的顺序,给出广义线段树上所有非叶子节点的划分位置 $m$。你也可以理解为从只有 $[1, n]$ 根节点开始,每次读入一个整数后,就将当前包含这个整数的节点做一次拆分,最后获得一棵有 $2n − 1$ 个节点的广义线段树。

保证给定的 $n − 1$ 个整数是一个排列,不难发现通过这些信息就能唯一确定一棵 $[1, n]$ 上的广义线段树。

输出格式

输出一行一个整数,代表期望数量对 $p = 998244353$ 取模后的结果。即,如果期望数量的最简分数表示为 $\frac ab$,你需要输出一个整数 $c$ 满足 $c\times b \equiv a \pmod p$。

样例一

input

3 1
1 2

output

166374060

explanation

输入的线段树为 $[1, 3], [1, 1], [2, 3], [2, 2], [3, 3]$。

若操作为 $[1, 1]/[2, 2]/[3, 3]/[2, 3]/[1, 3]$,标记个数为 $1$。若操作为 $[1, 2]$,标记个数为 $2$。故答案为 $\frac 76$。

样例二

input

5 4
2 1 3 4

output

320443836

样例三

见附加文件中 ex_segment3.inex_segment3.ans

限制与约定

测试点 $n$ $k$ 其他约定
$1$ $\le 10$ $\le 4$
$2$ $\le 10$ $\le 100$
$3$ $\le 5$ $\leq10^9$
$4$ $\leq 200000$ $=1$
$5$ $=32$ $\leq10^9$ 输入的线段树为完全二叉树
$6$ $=64$
$7$ $=4096$
$8$ $\le 5000$ 每个 $m$ 均在 $[l, r-1]$ 内均匀随机
$9$ $\le 100000$
$10$ $\leq 200000$

对于 $100\%$ 的数据,$1\le n\le 200000, 1\le k\le 10^9$。

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

空间限制:$512\texttt{MB}$

下载

样例数据下载