【集训队作业2018】count - 题目

如果一个序列满足序列长度为 $n$ ，序列中的每个数都是 $1$ 到 $m$ 内的整数，且所有 $1$ 到 $m$ 内的整数都在序列中出现过，则称这是一个挺好序列。

对于一个序列 $A$ ，记 $f_{A} (l, r)$ 为 $A$ 的第 $l$ 个到第 $r $ 个数中最大值的下标（如果有多个最大值，取下标最小的）。

两个序列 $A$ 和 $B$ 同构，当且仅当 $A$ 和 $B$ 长度相等，且对于任意 $i \leq j$ ，均有 $f_{A} (i, j) = f_{B} (i, j)$ 。

给出 $n, m$ ，求有多少种不同构的挺好序列。答案对 $998244353 $ 取模。

输入格式

一行两个正整数 $n, m$ 。

输出格式

一行一个整数，表示有多少种不同构的挺好序列。

样例一

input

3 2

output

explanation

一共 $6$ 种挺好序列： $2 1 1$ ， $1 2 1$ ， $1 1 2$ ， $1 2 2$ ， $2 1 2$ ， $2 2 1$ 。其中 $2 1 1$ 和 $2 2 1$ 同构， $1 2 1$ 和 $1 2 2$ 同构，所以一共有 $4$ 种不同构的挺好序列。

样例二

input

8 5

output

样例三

input

100000 99999

output

944488805

样例四

input

300 200

output

430256456

样例五

input

2000 1000

output

267823945

样例六

input

100000 50000

output

779381353

限制与约定

子任务	$n, m \leq$	特殊性质	分值
1	$8$		$10$
2	$100000$	$m \geq n - 1$	$10$
3	$300$		$30$
4	$2000$		$20$
5	$100000$		$30$

时间限制： $5s$

空间限制： $512MB$

下载

样例数据下载

Universal Online Judge

UOJ

#424. 【集训队作业2018】count

输入格式

输出格式

样例一

input

output

explanation

样例二

input

output

样例三

input

output

样例四

input

output

样例五

input

output

样例六

input

output

限制与约定

下载