UOJ Logo Universal Online Judge

UOJ

#473. 【CTS2019】珍珠

统计

白云苍狗,沧海桑田。

白云的眼前只剩下了模糊的一片。

在若隐若现之中,它看到了一个个小小的珍珠,有一些发着五彩的光芒。这些珍珠是白兔留下来的,每颗珍珠有一个颜色,为 $D$ 种颜色中随机的一种。

白云想把这些珍珠放进一些小瓶子中,每个瓶子能恰好容纳两颗珍珠。不过它也有要求,每个瓶子必须装满,并且装的都是相同颜色的珍珠。

白云希望能得到至少 $m$ 个装满珍珠的瓶子,它想知道它的愿望能被实现的概率是多少呢?

有 $n$ 个在范围 $[1,D]$ 内的整数均匀随机变量。

求至少能选出 $m$ 个瓶子,使得存在一种方案,选择一些变量,并把选出来的每一个变量放到一个瓶子中,满足每个瓶子都恰好装两个值相同的变量的概率。

请输出概率乘上 $D^n$ 后对 $998244353$ 取模的值。取模部分说明可参考第一题(随机立方体)

输入格式

输入仅一行,三个用空格隔开的整数 $D,n,m$。

输出格式

输出一个整数,表示所求概率乘上 $D^n$ 后对 $998244353$ 取模的结果。

样例一

input

2 2 1

output

2

explanation

情况 $1$ : 第一个变量为 $1$,第二个变量为 $1$。

情况 $2$ : 第一个变量为 $1$,第二个变量为 $2$。

情况 $3$ : 第一个变量为 $2$,第二个变量为 $1$。

情况 $4$ : 第一个变量为 $2$,第二个变量为 $2$。

其中情况 $1$ 和 $4$ 可以把两个变量放到一个瓶子中。

情况 $2$ 和 $3$ 中两个变量的值不相同,所以不能放到同一个瓶子中。

样例二至样例三

见样例数据下载。

限制与约定

对于所有测试数据: $0\le m\le 10^9,1\le n\le 10^9,1\le D\le 10^5$。

每个测试点的具体限制见下表:

测试点编号$D $ $n $ $m $
$1$$\le 2$$\le 10$$\le n$
$2$$\le 2$$\le 20$$\le n$
$3$$\le 100$$\le 100$$\le n$
$4$$\le 100$$\le 100$$\le n$
$5$$\le 100$$\le 100$$\le n$
$6$$\le 100$$\le 100$$\le n$
$7$$\le 100$$\le 100$$\le n$
$8$$\le 4000$$\le 4000$$\le n$
$9$$\le 4000$$\le 4000$$\le n$
$10$$\le 4000$$\le 4000$$\le n$
$11$$\le 4000$$\le 4000$$\le n$
$12$$\le 4000$$\le 4000$$\le n$
$13$$\le 300$$\le 1000000000$$\le n$
$14$$\le 300$$\le 1000000000$$\le n$
$15$$\le 300$$\le 1000000000$$\le n$
$16$$\le 100000$$\le 1000000000$$\le 0$
$17$$\le 100000$$\le 1000000000$$\le 1$
$18$$\le 100000$$\le 1000000000$$\le 2$
$19$$\le 100000$$\le 1000000000$$\le n$
$20$$\le 100000$$\le 1000000000$$\le n$
$21$$\le 100000$$\le 1000000000$$\le n$
$22$$\le 100000$$\le 1000000000$$\le n$
$23$$\le 100000$$\le 1000000000$$\le n$
$24$$\le 100000$$\le 1000000000$$\le n$
$25$$\le 100000$$\le 1000000000$$\le n$

时间限制: 1s

空间限制: 512MB

下载

样例数据下载