「EZEC-7」线段树

Bob 喜欢线段树。

如果你不知道线段树，可以看 提示说明 中的定义。 Bob 得到了一个长度为 $n$ 的序列 $a_{1,2,\cdots,n}$，初始全为 $0$。 接着 Bob 进行了 $m$ 次区间加操作，每次操作会等概率地从 $[1,n]$ 的所有 $\dfrac{n(n+1)}{2}$ 个子区间中随机选择一个进行操作，每次加的数是 $[-1,V]$ 之间等概率随机的整数。 $m$ 次操作完之后要求出每一个位置的值。 由于 Bob 喜欢线段树，他熟练地打出一颗 $[1,n]$ 上的线段树来解决这个问题，使用懒惰标记来解决区间加的问题。 打代码的过程中 Bob 忽然想到了两个减小 $\mathrm{Pushdown}$（下传懒惰标记）次数的方法： + 修改的时候不 $\mathrm{Pushdown}$，最后一次性 $\mathrm{Pushdown}$（即 $\mathrm{Pushall}$ 函数）。 + $\mathrm{Pushall}$ 到一个节点的时候，如果这个节点的懒惰标记为 $0$ 那么不 $\mathrm{Pushdown}$。 现在 Bob 想知道期望 $\mathrm{Pushdown}$ 次数，可是他不会算，于是来问你。 下面是 Bob 写的线段树伪代码（其中 `tag` 数组为懒惰标记）： $ \displaystyle \begin{array}{l} \mathrm{pushdown\_counter}\leftarrow 0\\ \\ \textbf{function }\mathrm{Update(Node},l,r,ql,qr,Delta)\\ \qquad \textbf{if } [l,r]\cap [ql,qr] = \varnothing \textbf{ then}\\ \qquad \qquad \textbf{return}\\ \qquad \textbf{end if}\\ \qquad \textbf{if }[l,r] \subseteq [ql,qr] \textbf{ then}\\ \qquad \qquad \mathrm{tag[Node]\leftarrow tag[Node]}+Delta\\ \qquad \qquad \textbf{return}\\ \qquad \textbf{end if}\\ \qquad mid\leftarrow \lfloor\dfrac{l+r}{2}\rfloor\\ \qquad \mathrm{Update(LeftChild},l,mid,ql,qr,Delta)\\ \qquad \mathrm{Update(RightChild},mid+1,r,ql,qr,Delta)\\ \textbf{end function}\\ \\ \textbf{function }\mathrm{Pushdown(Node)} \\ \qquad \mathrm{tag[LeftChild]\leftarrow tag[LeftChild]+tag[Node]}\\ \qquad \mathrm{tag[RightChild]\leftarrow tag[RightChild]+tag[Node]}\\ \qquad \mathrm{pushdown\_counter}\leftarrow \mathrm{pushdown\_counter}+1\\ \textbf{end function}\\ \\ \textbf{function }\mathrm{Pushall(Node},l,r)\\ \qquad \textbf{if } \mathrm{Node\ is\ Leaf} \textbf{ then}\\ \qquad \qquad \textbf{return}\\ \qquad \textbf{end if}\\ \qquad \textbf{if } \mathrm{tag[Node] \not= 0} \textbf{ then}\\ \qquad \qquad \mathrm{Pushdown(Node)}\\ \qquad \textbf{end if}\\ \qquad mid\leftarrow \lfloor\dfrac{l+r}{2}\rfloor\\ \qquad \mathrm{Pushall(LeftChild},l,mid)\\ \qquad \mathrm{Pushall(RightChild},mid+1,r)\\ \textbf{end function} \end{array} $ 换句话说，你要帮 Bob 求出 `pushdown_counter` 的期望值。 答案对 $998244353$ 取模。

一行三个整数 $n,m,V$。

一个整数，期望 $\mathrm{Pushdown}$ 次数对 $998244353$ 取模的结果。

2 1 0

166374059

2 2 1

813384288

3 2 1

462150164

100 114 514

718571152

**【样例解释 #1】** 整颗线段树只有 $3$ 个节点：$[1,2],[1,1],[2,2]$。 只有节点 $[1,2]$ 可能 $\mathrm{Pushdown}$。 当操作为 $\mathrm{Update(1,2,-1)}$ 的时候，根节点的懒惰标记为 $-1$， $\mathrm{Pushall}$ 在根号节点会 $\mathrm{Pushdown}$；而 $\mathrm{Update(1,2,0)}$ 之后，由于根节点懒惰标记为 $0$ 不 $\mathrm{Pushdown}$。 其余 $4$ 种操作均把懒惰标记打在叶子节点，即 $\mathrm{Update(1,1,-1)},\mathrm{Update(1,1,0)},\mathrm{Update(2,2,-1)},\mathrm{Update(2,2,0)}$，不会 $\mathrm{Pushdown}$。 所以，总共 $6$ 种情况，能 $\mathrm{Pushdown}$ 的只有 $1$ 种，期望次数为 $\dfrac{1}{6}$。 **【样例解释 #2】** 由于情况过多，不一一解释，只解释一种情况。 如果执行的 $2$ 次操作分别为 $\mathrm{Update(1,2,-1)},\mathrm{Update(1,2,1)}$，由于这时候根节点的懒惰标记为 $0$，在 $\mathrm{Pushall}$ 的时候仍然不会 $\mathrm{Pushdown}$。 --------- **【数据范围】** **本题采用捆绑测试。** | 子任务编号 | $n\le$ | $m\le$ | $V$ | 分值 | 时间限制$\text{ / ms}$ | | :----: | :------------: | :------------: | :-----------------: | :----: | :--------: | | $1$ | $4$ | $4$ | $\le 2$ | $3$ | $500$ | | $2$ | $300$ | $300$ | $\le 300$ | $7$ | $500$ | | $3$ | $1000$ | $1000$ | $\le 1000$ | $10$ | $500$ | | $4$ | $300$ | $10^5$ | $=1000$ | $15$ | $2000$ | | $5$ | $10^5$ | $10^5$ | $\le 0$ | $10$ | $3000$ | | $6$ | $10^5$ | $10^5$ | $=1000$ | $15$ | $3000$ | | $7$ | $10^5$ | $10^5$ | $\le 998244350$ | $40$ | $3000$ | 对于 $100\%$ 的数据，$1 \le n \le 10^5$，$1 \le m \le 10^5$，$-1 \le V \le 998244350$。 ---------- **【线段树定义】** 线段树是一棵每个节点上都记录了一个线段的二叉树。根节点记录的线段是 $[1, n]$。对于每个节点，若它记录的线段是 $[l, r]$ 且 $l\not= r$，取 $m = \lfloor \dfrac{l+r}{2} \rfloor$，则它的左右儿子节点记录的线段分别是 $[l, m]$ 和 $[m+1,r]$；若 $l=r$，则它是叶子节点。