Logo Quest Online Judge

QOJ

时间限制:1 s 空间限制:512 MB

#2188. 小C的线段树

统计

题目描述

在跟他大哥sxy cnyali学习了线段树后,善于思考的小C想到了这样一个问题.

小C有一个长度为 $m$ 的序列 $A$ ,初始全为 $0$ . 现在有 $n$ 个操作,每个操作会给出一个左闭 右开的区间$[l, r)$, $1 \leq l \leq r \leq m$ ,小C会把区间内的所有数$+1$. $n$个操作全部进行完之后,小C会询问 $ans$ 的值:

$$ans=\sum_{i=1}^mA_{i}^{k}$$

小C的数据生成器十分特殊,它会生成 $n$ 个区间$[l_1 , r_1 ), \dots , [l_n , r_n)$ 作为操作区间,且满足$l_i < l_{i+1}$ , $r_i < r_{i+1}$ , $1 \leq l_i \leq r_i \leq m$.

现在小C想知道,对于所有可能生成出的操作区间序列, $ans$ 的和是多少.

输入格式

一行三个整数 $n$ , $m$ , $k$.

输出格式

一个整数表示答案对 $998244353$ 取模的结果.

样例

样例输入1

2 3 3

样例输出1

4

样例解释1

可能的操作序列有五种: $\{[1, 1), [2, 2)\}$, $\{[1, 1), [2, 3)\}$, $\{[1, 2), [2, 3)\}$,$\{[1, 2), [3, 3)\}$, $\{[2, 2), [3, 3)\}$.

样例输入2

12 20 1

样例输出2

636776227

数据范围与提示

对于所有数据满足$1 \leq nm \leq 10^5$ , $1 \leq n, m \leq 10^5$ , $1 \leq k \leq 10^9$.

本题共$20$个测试点,每个测试点$5$分.各个测试点还满足:

1.png