← 返回题目列表

Codeforces · 1930/E

E. 2..3...4.... 太棒了!精彩的!

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

Stack 有一个长度为 $$$n$$$ 的数组 $$$a$$$,对于所有 $$$i$$$,$$$a_i = i$$$ ($$$1 \leq i \leq n$$$)。他将选择一个正整数 $$$k$$$ ($$$1 \leq k \leq \lfloor \frac{n-1}{2} \rfloor$$$) 并对 $$$a$$$ 任意次数(可能是 $$$0$$$)执行以下操作。

- 从 $$$a$$$ 中选择长度为 $$$2 \cdot k + 1$$$ 的子序列$$$^\dagger$$$ $$$s$$$。现在,他将从 $$$a$$$ 中删除 $$$s$$$ 的前 $$$k$$$ 个元素。为了保持完美平衡(所有事情都应该如此),他还将从 $$$a$$$ 中删除 $$$s$$$ 的最后 $$$k$$$ 元素。

Stack 想知道对于每个 $$$k$$$ ($$$1 \leq k \leq \lfloor \frac{n-1}{2} \rfloor$$$),他最终能得到多少个数组 $$$a$$$。由于 Stack 不擅长计算问题,因此他需要你的帮助。

由于数组数量可能太大,请以 $$$998\,244\,353$$$ 为模打印。

$$$^\dagger$$$ 序列 $$$x$$$ 是序列 $$$y$$$ 的子序列,如果 $$$x$$$ 可以通过删除多个(可能是零个或全部)元素从 $$$y$$$ 获得。例如,$$$[1, 3]$$$、$$$[1, 2, 3]$$$ 和 $$$[2, 3]$$$ 是 $$$[1, 2, 3]$$$ 的子序列。另一方面,$$$[3, 1]$$$ 和 $$$[2, 1, 3]$$$ 不是 $$$[1, 2, 3]$$$ 的子序列。

输入

每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^3$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$3 \leq n \leq 10^6$$$) — 数组 $$$a$$$ 的长度。

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

输出

对于每个测试,在新行上打印 $$$\lfloor \frac{n-1}{2} \rfloor$$$ 空格分隔的整数 - 第 $$$i$$$ 整数表示以 $$$998\,244\,353$$$ 为模的数组数量,如果 Stack 选择 $$$k=i$$$,则 Stack 可以获得该数。

示例

输入 #1

4
3
4
5
10

输出 #1

2 
4 
10 2 
487 162 85 10

注意

在第一个测试用例中,$$$a$$$ 可能有两个 $$$k=1$$$:

- $$$[1,2,3]$$$;
- $$$[2]$$$.

在第二个测试用例中,$$$k=1$$$ 可能有四个 $$$a$$$:

- $$$[1,2,3,4]$$$;
- $$$[1,3]$$$;
- $$$[2,3]$$$;
- $$$[2,4]$$$.

在第三个测试用例中,对于 $$$k=2$$$ 来说,两个 $$$a$$$ 是可能的:

- $$$[1,2,3,4,5]$$$;
- $$$[3]$$$.