#P6630. [ZJOI2020] 传统艺能

[ZJOI2020] 传统艺能

题目背景

4s,512MB

题目描述

Bob 喜欢线段树。

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

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

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

【具体定义】

线段树:线段树是一棵每个节点上都记录了一个线段的二叉树。根节点记录的线段是 [1,n][1, n]。对于每个节点,若它记录的线段是 [l,r][l, r]lrl \neq r,取 m=l+r2m = \lfloor \dfrac{l+r}{2} \rfloor,则它的左右儿子节点记录的线段分别是 [l,m][l, m][m+1,r][m + 1, r];若 l=rl = r,则它是叶子节点。

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

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

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

你也可以这么理解题意:有一棵广义线段树,每个节点有一个 mm 值。一开始 tag 数组均为 00,Bob 会执行 kk 次操作,每次操作等概率随机选择区间 [l,r][l, r] 并执行 MODIFY(root,1,n,l,r);。 最后所有 Node 中满足 tag[Node]=1 的期望数量就是需要求的值。

输入格式

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

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

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

输出格式

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

3 1
1 2
166374060
5 4
2 1 3 4
320443836

提示

样例输入输出 33 见下发文件。

样例解释 11

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

若操作为 [1,1]/[2,2]/[3,3]/[2,3]/[1,3][1, 1]/[2, 2]/[3, 3]/[2, 3]/[1, 3],标记个数为 11。若操作为 [1,2][1, 2],标记个数为 22。故答案为 76\dfrac{7}{6}

测试点 nn kk 其他约定
11 10\leq 10 4\leq 4
22 100\leq 100
33 5\leq 5
44 =1=1
55 =32=32 输入的线段树为完全二叉树
66 =64=64
77 =4096=4096
88 5000\leq 5000 每个 mm 均在 [l,r1][l, r - 1] 内均匀随机
99 100000\leq 100000
1010

对于 100%100\% 的数据,1n200000,1k1091 \leq n \leq 200000, 1 \leq k \leq 10^9