QOJ.ac

QOJ

Time Limit: 5 s Memory Limit: 512 MB Total points: 100 Hackable ✓

#13624. count

Statistics

如果一个序列满足序列长度为$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$

Discussions

About Discussions

The discussion section is only for posting: Editorials, General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues. Submitting multiple issues may cause your account to be banned.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.