← 返回题目列表

Codeforces · 1644/F

F. 基础

中文机器翻译题面 查看原题

对于整数数组 $$$a$$$,我们将 $$$|a|$$$ 定义为其中的元素数量。

让我们表示两个函数:

- $$$F(a, k)$$$ 是一个函数,它接受整数数组 $$$a$$$ 和正整数 $$$k$$$。此函数的结果是包含 $$$|a|$$$ 数组的第一个元素的数组,通过将 $$$a$$$ 的每个元素替换为该元素的 $$$k$$$ 副本而获得。例如,$$$F([2, 2, 1, 3, 5, 6, 8], 2)$$$ 计算如下:首先,将数组的每个元素替换为 $$$2$$$ 的副本,因此您获得$$$[2,2,2,2,1,1,3,3,5,5,6,6,8,8]$$$。然后,取出获得的数组的前 $$$7$$$ 元素,因此该函数的结果为 $$$[2, 2, 2, 2, 1, 1, 3]$$$。
- $$$G(a, x, y)$$$ 是一个函数,它接受整数数组 $$$a$$$ 和两个不同的整数 $$$x$$$ 和 $$$y$$$。该函数的结果是数组 $$$a$$$,其中等于 $$$x$$$ 的每个元素都替换为 $$$y$$$,等于 $$$y$$$ 的每个元素都替换为 $$$x$$$。例如,$$$G([1, 1, 2, 3, 5], 3, 1) = [3, 3, 2, 1, 5]$$$。

数组 $$$a$$$ 是数组 $$$b$$$ 的父数组,如果:

- 要么存在正整数 $$$k$$$ 使得 $$$F(a, k) = b$$$;
- 或者存在两个不同的整数 $$$x$$$ 和 $$$y$$$ 使得 $$$G(a, x, y) = b$$$。

如果存在数组 $$$c_0, c_1, \dots, c_m$$$ ($$$m \ge 0$$$) 的有限序列,使得 $$$c_0$$$ 是 $$$a$$$,$$$c_m$$$ 是 $$$b$$$,并且对于每个$$$i \in [1, m]$$$, $$$c_{i-1}$$$ 是 $$$c_i$$$ 的父级。

现在,问题本身。

给你两个整数 $$$n$$$ 和 $$$k$$$。您的目标是构造一个数组序列 $$$s_1, s_2, \dots, s_m$$$ ,方式如下:

- 每个数组 $$$s_i$$$ 恰好包含 $$$n$$$ 个元素,并且所有元素都是从 $$$1$$$ 到 $$$k$$$ 的整数;
- 对于每个由 $$$1$$$ 到 $$$k$$$ 之间的 $$$n$$$ 整数组成的数组 $$$a$$$,该序列至少包含一个数组 $$$s_i$$$,使得 $$$s_i$$$ 是 $$$a$$$ 的祖先。

打印该序列中数组的最小数量。

输入

唯一的一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n, k \le 2 \cdot 10^5$$$)。

输出

打印一个整数 — 满足约束的数组序列中元素的最小数量。由于答案可能很大,因此输出它对 $$$998244353$$$ 取模。

示例

输入 #1

3 2

输出 #1

2

输入 #2

4 10

输出 #2

12

输入 #3

13 37

输出 #3

27643508

输入#4

1337 42

输出#4

211887828

输入 #5

198756 123456

输出 #5

159489391

输入 #6

123456 198756

输出 #6

460526614

注意

我们来分析第一个例子。

第一个示例的可能答案之一是序列 $$$[[2, 1, 2], [1, 2, 2]]$$$。每个大小为 $$$3$$$ 的数组由从 $$$1$$$ 到 $$$2$$$ 的元素组成,其祖先序列如下:

- 对于数组 $$$[1, 1, 1]$$$,祖先是 $$$[1, 2, 2]$$$: $$$F([1, 2, 2], 13) = [1, 1, 1]$$$;
- 对于数组 $$$[1, 1, 2]$$$,祖先是 $$$[1, 2, 2]$$$: $$$F([1, 2, 2], 2) = [1, 1, 2]$$$;
- 对于数组 $$$[1, 2, 1]$$$,祖先是 $$$[2, 1, 2]$$$: $$$G([2, 1, 2], 1, 2) = [1, 2, 1]$$$;
- 对于数组$$$[1, 2, 2]$$$,祖先是$$$[1, 2, 2]$$$;
- 对于数组 $$$[2, 1, 1]$$$,祖先是 $$$[1, 2, 2]$$$: $$$G([1, 2, 2], 1, 2) = [2, 1, 1]$$$;
- 对于数组 $$$[2, 1, 2]$$$,祖先是 $$$[2, 1, 2]$$$;
- 对于数组 $$$[2, 2, 1]$$$,祖先是 $$$[2, 1, 2]$$$: $$$F([2, 1, 2], 2) = [2, 2, 1]$$$;
- 对于数组 $$$[2, 2, 2]$$$,祖先是 $$$[1, 2, 2]$$$:$$$G(F([1, 2, 2], 4), 1, 2) = G([1, 1, 1], 1, 2) = [2, 2, 2]$$$。