UOJ Logo Universal Online Judge

UOJ

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

统计

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

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

两个序列$A$和$B$同构,当且仅当$A$和$B$长度相等,且对于任意$i\le j$,均有$f_A(i,j)=f_B(i,j)$。

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

输入格式

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

输出格式

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

样例一

input

3 2

output

4

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

1341

样例三

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\ge n-1$ $10$
3 $300$ $30$
4 $2000$ $20$
5 $100000$ $30$

时间限制:$\texttt{5s}$

空间限制:$\texttt{512MB}$

下载

样例数据下载