首先我们设 $g_x$ 为 x 对情侣没有一对坐在一起的方案数（这里的方案数仅考虑这 x 对情侣，不考虑其余情侣）
然后答案就可以表示成：$C_n^k*A_n^k*2^k*g_{n-k}$
这里的复杂度是 $O(T*N)$ ，貌似不错，所以现在问题变成求 $g_x$ 了
第一篇题解是利用这是一个错排问题，用递推式解决，复杂度为优秀的 $O(N)$ ，但是由于询问的复杂度已经是 $O(T*N)$ 了，假设我们并不知道这个递推式，我们还能怎么做呢？
考虑暴力容斥：
所有的情况是 $(2*x)!$ ，然后一对以上情侣数量为 $C_x^1*(2*x-2)!*2*A_x^1$ ，意义是：我可以在 x 对中选取一对，其他的 $x-1$ 对是随便坐的，然后这对情侣可以交换位置，并且占领 $A_x^1$ 排位置
然后两对以上，三对以上也是同理，每一对情侣都可以交换位置，在 x 对中选择 i 对，其余 $(x-i)$ 对共 $2*(x-i)$ 个人，随便坐，方案数为 $(2*x-2*i)!$ ，求出来以后直接容斥就好了，所以整体的柿子长成这样：
$$g_x=\sum_{i=0}^x(-1)^i\times 2^i\times C_x^i\times (2\times x-2\times i)!$$
这个式子暴力去算就好了，复杂度 $O(N^2)$ ，所以整体复杂度还是 $O(N^2)$
## $Code:$
```
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define re register
#define mod 998244353
il int read() {
re int x = 0, f = 1; re char c = getchar();
while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
return x * f;
}
#define rep(i, s, t) for(re int i = s; i <= t; ++ i)
#define maxn 1005
int pai[maxn << 1], inv[maxn << 1], g[maxn];
il int mul(int a, int b) {
return 1ll * a * b % mod;
}
il int qpow(int a, int b) {
int r = 1;
while(b) {
if(b & 1) r = mul(a, r);
a = mul(a, a), b >>= 1;
}
return r;
}
il int C(int n, int m) {
return mul(mul(pai[n], inv[m]), inv[n - m]);
}
il int A(int n, int m) {
return mul(pai[n], inv[n - m]);
}
il void solve(int x) {
rep(i, 0, x) printf("%d\n", mul(mul(C(x, i), qpow(2, i)), mul(A(x, i), g[x - i])));
}
il int get(int x) {
int ans = 0;
rep(i, 0, x) {
int x1 = mul(pai[x], inv[i]), x2 = mul(pai[2 * x - 2 * i], inv[x - i]);
ans = (ans + mul(mul(mul(x1, x2), qpow(-2, i)), A(x, i))) % mod;
}
return (ans + mod) % mod;
}
int main() {
pai[0] = inv[0] = pai[1] = inv[1] = 1, g[0] = 1, g[1] = 0;
rep(i, 2, 2000) pai[i] = mul(pai[i - 1], i), inv[i] = qpow(pai[i], mod - 2);
rep(i, 2, 1000) g[i] = get(i);
int T = read();
while(T --) solve(read());
return 0;
}
```