AT_abc237_f.[ABC237F] |LIS| = 3

提高+/省选-

通过率:0%

AC君温馨提醒

该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

请计算满足以下所有条件的数列数量,结果对 998244353998244353 取模:

  • 数列长度为 NN
  • 数列的每个元素是 11 到 MM 之间的整数
  • 最长递增子序列(LIS)的长度恰好为 33

输入格式

输入通过标准输入给出,格式如下:

NN MM

输出格式

输出答案。

输入输出样例

  • 输入#1

    4 5

    输出#1

    135
  • 输入#2

    3 4

    输出#2

    4
  • 输入#3

    111 3

    输出#3

    144980434

说明/提示

注释

数列的子序列是指从原数列中删除 00 个或多个元素后,将剩余元素按原顺序连接得到的数列。
例如,(10,30)(10,30) 是 (10,20,30)(10,20,30) 的子序列,而 (20,10)(20,10) 不是 (10,20,30)(10,20,30) 的子序列。

数列的最长递增子序列是指该数列的所有严格单调递增子序列中长度最大的那个。

约束条件

  • 3≤N≤10003 \leq N \leq 1000
  • 3≤M≤103 \leq M \leq 10
  • 输入均为整数

样例解释 1

例如 (3,4,1,5)(3,4,1,5) 是符合条件的数列。而 (4,4,1,5)(4,4,1,5) 的最长递增子序列长度为 22,因此不符合条件。

样例解释 3

请确保结果对 998244353998244353 取模。

翻译由 DeepSeek R1 完成

输入解题思路,AI测评打分。不知道怎么写?

首页