102375: [AtCoder]ABC237 F - |LIS| = 3

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:1 Solved:0

Description

Score : $500$ points

Problem Statement

Find the number of sequences that satisfy all of the conditions below, modulo $998244353$.

  • The length is $N$.
  • Each of the elements is an integer between $1$ and $M$ (inclusive).
  • Its longest increasing subsequence has the length of exactly $3$.

Notes

A subsequence of a sequence is the result of removing zero or more elements from it and concatenating the remaining elements without changing the order. For example, $(10,30)$ is a subsequence of $(10,20,30)$, while $(20,10)$ is not a subsequence of $(10,20,30)$.

A longest increasing subsequence of a sequence is its strictly increasing subsequence with the greatest length.

Constraints

  • $3 \leq N \leq 1000$
  • $3 \leq M \leq 10$
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$ $M$

Output

Print the answer.


Sample Input 1

4 5

Sample Output 1

135

One sequence that satisfies the conditions is $(3,4,1,5)$.
On the other hand, $(4,4,1,5)$ do not, because its longest increasing subsequence has the length of $2$.


Sample Input 2

3 4

Sample Output 2

4

Sample Input 3

111 3

Sample Output 3

144980434

Find the count modulo $998244353$.

Input

题意翻译

请求出满足以下条件的数列的个数: - 数列长度为 $ N $ - 数列各项为 $ 1 $ 以上 $ M $ 以下的整数 - 最长增加部分列长度正好为 $ 3 $ 请输出答案对 $998244353$ 取模的结果。

Output

得分:500分 部分 问题描述 求满足以下所有条件的序列的数量,对998244353取模。
  • 长度为N。
  • 每个元素都是1到M(包括)之间的整数。
  • 它的最长递增子序列的长度正好为3。
部分 注意 序列的< strong>子序列是从其中删除零个或多个元素并将剩余元素按顺序连接的结果。 例如,(10,30)是(10,20,30)的子序列,而(20,10)不是(10,20,30)的子序列。 序列的< strong>最长递增子序列是其< strong>严格递增子序列中的最大长度。 部分 约束
  • 3≤N≤1000
  • 3≤M≤10
  • 输入中的所有值都是整数。
部分 输入格式 输入以标准输入的以下格式给出: N M 部分 输出格式 输出答案。 部分 样例输入1 4 5 部分 样例输出1 135 一个满足条件的序列是(3,4,1,5)。 另一方面,(4,4,1,5)不满足条件,因为它的最长递增子序列的长度为2。 部分 样例输入2 3 4 部分 样例输出2 4 部分 样例输入3 111 3 部分 样例输出3 144980434 对998244353取模求计数。

加入题单

上一题 下一题 算法标签: