← 返回题目列表

Codeforces · 2222/H

H. 计数排序?

中文机器翻译题面 查看原题
我想在决定性的时刻冲动地结束这一生,而不是生活在为我安排的轨道上。
香椎梦美&可爱由纪, 决定性的时刻

对于数组 $$$[b_1, b_2, \ldots, b_m]$$$,其中 $$$0 \le b_i \le m$$$,将 $$$f(b)$$$ 定义为数组 $$$[c_1, c_2, \ldots, c_m]$$$,这样 $$$c_i$$$ 是出现的次数$$$i$$$ 在数组 $$$b$$$ 中。

定义 值 $$$g(b)$$$ 的数组 $$$[b_1, b_2, \ldots, b_m]$$$,其中 $$$0 \le b_i \le m$$$,如下所示:

  • 最初,有一个空集$$$S$$$。创建一个数组 $$$d$$$,最初等于 $$$b$$$。
  • 然后,执行以下操作$$$100^{100}$$$次:将$$$d$$$插入$$$S$$$,然后设置$$$d \gets f(d)$$$。
  • $$$g(b)$$$ 是操作后$$$S$$$ 中不同数组的数量。

现在给你两个整数 $$$n$$$ 和 $$$k$$$,以及一个数组 $$$[r_1, r_2, \ldots, r_n]$$$。对于每个 $$$1\le p\le k$$$,计算数组 $$$[a_1, a_2, \ldots, a_n]$$$ 的数量,其中 $$$0 \le a_i \le r_i$$$ 使得 $$$g(a) = p$$$。由于这个数字可能很大,因此输出它对 $$$998\,244\,353$$$ 取模。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1000$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 50$$$, $$$1 \le k \le 1000$$$)。

第二行包含 $$$n$$$ 整数 $$$r_1, r_2, \ldots, r_n$$$ ($$$0 \le r_i \le n$$$)。

保证所有测试用例的$$$n^3$$$总和不超过$$$50^3$$$。

输出

对于每个测试用例,输出 $$$k$$$ 整数 - 数组 $$$[a_1, a_2, \ldots, a_n]$$$ 与 $$$0 \le a_i \le r_i$$$ 的数量,使得 $$$g(a) = 1, 2, \ldots, k$$$ 分别。

打印以 $$$998\,244\,353$$$ 为模的答案。

示例

输入
复制

6
2 5
2 2
5 6
4 5 1 4 5
7 7
7 6 5 5 6 7 6
11 7
5 8 9 10 11 4 10 11 7 8 11
12 7
12 12 12 12 12 12 12 12 12 12 12 12
5 10
0 0 0 0 1

输出
复制

2 1 2 2 2
2 4 14 60 554 395
2 6 35 627 63856 171611 490235
2 10 83 10495 286935908 71004446 630281080
2 11 132 48996 207819517 474452948 13828302
1 1 0 0 0 0 0 0 0 0

注意

在第一个测试用例中, $$$g([0, 0]) = g([1, 0]) = 1$$$, $$$g([0, 1]) = 2$$$, $$$g([2, 0]) = g([0, 2]) = 3$$$, $$$g([1, 1]) = g([2, 2]) = 4$$$ 和 $$$g([1, 2]) = g([2, 1]) = 5$$$。

在第二个测试用例中, $$$f([4, 5, 1, 4, 5]) = [1, 0, 0, 2, 2]$$$, $$$f([1, 0, 0, 2, 2]) = [1, 2, 0, 0, 0]$$$, $$$f([1, 2, 0, 0, 0]) = [1, 1, 0, 0, 0]$$$, $$$f([1, 1, 0, 0, 0]) = [2, 0, 0, 0, 0]$$$, $$$f([2, 0, 0, 0, 0]) = [0, 1, 0, 0, 0]$$$, $$$f([0, 1, 0, 0, 0]) = [1, 0, 0, 0, 0]$$$, $$$f([1, 0, 0, 0, 0]) = [1, 0, 0, 0, 0]$$$。所以,$$$g([4, 5, 1, 4, 5]) = 7$$$。