QOJ.ac

QOJ

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

#13624. 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$
About Issues

We understand that our problem archive is not perfect. If you find any issues with the problem, including the statement, scoring configuration, time/memory limits, test cases, etc.

You may use this form to submit an issue regarding the problem. A problem moderator will review your issue and proceed it properly.

STOP! Before you submit an issue, please READ the following guidelines:

  1. This is not a place to publish a discussion, editorial, or requests to debug your code. Your issue will only be visible by you and problem moderators. Other users will not be able to view or reply your issues.
  2. Do not submit duplicated issues. If you have already submitted one, please wait for an moderator to review it. Submitting multiple issues will not speed up the review process and might cause your account to be banned.
  3. Issues must be filed in English or Chinese only.
  4. Be sure your issue is related to this problem. If you need to submit an issue regarding another problem, contest, category, etc., you should submit it to the corresponding page.

Active Issues 0

No issues in this category.

Closed/Resolved Issues 0

No issues in this category.