P6630 [ZJOI2020] Traditional Skill

4 s, 512 MB

Bob likes segment trees. As everyone knows, the second problem of ZJOI contains many segment trees. Bob has a generalized segment tree whose root is $[1, n]$. Bob needs to perform $k$ range lazy-tag operations on this segment tree. Each operation uniformly at random selects one sub-interval from all $\dfrac{n(n+1)}{2}$ sub-intervals of $[1, n]$. For every non-leaf node visited during this operation, Bob will push down the tag on this node; for every leaf node (i.e. a node where the recursion does not continue), Bob will set a tag on this node. Bob wants to know: after $k$ operations, what is the expected number of nodes that have a tag. 【Precise definitions】 Segment tree: A segment tree is a binary tree where each node stores a segment. The root node stores the segment $[1, n]$. For each node, if it stores $[l, r]$ and $l \neq r$, let $m = \lfloor \dfrac{l+r}{2} \rfloor$, then its left and right children store $[l, m]$ and $[m + 1, r]$ respectively; if $l = r$, then it is a leaf node. Generalized segment tree: In a generalized segment tree, $m$ is not required to be exactly the midpoint of the interval, but it must still satisfy $l \leq m < r$. It is not hard to see that in a generalized segment tree, the depth of the tree can reach $O(n)$. The core of a segment tree is lazy tags. Below is pseudocode for a generalized segment tree with lazy tags, where the `tag` array represents lazy tags:  Note that when processing a leaf node, once it gets a tag, this tag will remain forever. You can also understand the problem as follows: There is a generalized segment tree, and each node has an $m$ value. Initially, all values in the `tag` array are $0$. Bob will perform $k$ operations. Each operation uniformly at random selects an interval $[l, r]$ and executes `MODIFY(root,1,n,l,r);`. In the end, the expected number of all `Node` such that `tag[Node]=1` is the value you need to compute.

The first line contains two integers $n, k$. The next line contains $n - 1$ integers $a_i$: in preorder traversal order, they give the split position $m$ of every non-leaf node in the generalized segment tree. You can also understand it like this: starting from a tree with only the root node $[1, n]$, each time you read an integer, you split the current node whose interval contains this integer once, and finally you obtain a generalized segment tree with $2n - 1$ nodes. It is guaranteed that the given $n - 1$ integers form a permutation. It is not hard to see that with this information, a unique generalized segment tree on $[1, n]$ can be determined.

Output one integer, representing the expected value modulo $p = 998244353$. That is, if the expected value in lowest terms is $\dfrac{a}{b}$, you need to output an integer $c$ such that $c \times b \equiv a \pmod p$.

The sample input/output for $3$ is provided in the attachment. Sample explanation $1$ The input segment tree is $[1, 3], [1, 1], [2, 3], [2, 2], [3, 3]$. If the operation is $[1, 1]/[2, 2]/[3, 3]/[2, 3]/[1, 3]$, the number of tagged nodes is $1$. If the operation is $[1, 2]$, the number of tagged nodes is $2$. Therefore, the answer is $\dfrac{7}{6}$. | Test Point | $n$ | $k$ | Other Constraints | | :----------: | :----------: | :----------: | :----------: | | $1$ | $\leq 10$ | $\leq 4$ | None | | $2$ | $\leq 10$ | $\leq 100$ | None | | $3$ | $\leq 5$ | None | None | | $4$ | None | $=1$ | None | | $5$ | $=32$ | None | The input segment tree is a complete binary tree | | $6$ | $=64$ | None | The input segment tree is a complete binary tree | | $7$ | $=4096$ | None | The input segment tree is a complete binary tree | | $8$ | $\leq 5000$ | None | Each $m$ is uniformly random in $[l, r - 1]$ | | $9$ | $\leq 100000$ | None | None | | $10$ | None | None | None | For $100\%$ of the data, $1 \leq n \leq 200000, 1 \leq k \leq 10^9$. Translated by ChatGPT 5