电影院排座(Couples in Cinema)

题目描述

FFF

本题加强版：P4931

有 $n$ 对情侣来到电影院观看电影。在电影院，恰好留有 $n$ 排座位，每排包含 $2$ 个座位，共 $2×n$ 个座位。

现在，每个人将会随机坐在某一个位置上，且恰好将这 $2 × n$ 个座位坐满。

如果一对情侣坐在了同一排的座位上，那么我们称这对情侣是和睦的。

你的任务是求出当 $k = 0, 1, ... , n$ 时，共有多少种不同的就坐方案满足恰好有 $k$ 对情侣是和睦的。

两种就坐方案不同当且仅当存在一个人在两种方案中坐在了不同的位置。不难发现，一共会有 $(2n)!$ 种不同的就坐方案。

由于结果可能较大，因此输出对 $998244353$ 取模的结果。

输入格式

输入包含多组数据。

输入的第 $1$ 行包含 $1$ 个正整数 $T(1 \leq T \leq 1000)$，表示数据的组数。

接下来 $T$ 行，每行包含 $1$ 个正整数 $n(1 \leq n \leq 1000)$。

输出格式

对于每组输入数据，输出共 $n + 1$ 行，每行包含 $1$ 个整数，分别表示 $k = 0, 1, ..., n$ 时满足恰好有 $k$ 对情侣是和睦的就坐方案数。

样例输入 #1

2
1
2

样例输出 #1

0
2
16
0
8

数据范围

子任务

本题只有一个 $T=1000$ 的数据点。。。暴力还是算了吧！

题目来源

MtOI2018 迷途の家の水题大赛 T2

出题人：Imagine

50167

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1900。

测试点分布

出处：原题链接