加强前这道题还是比较友好的
首先我们设(g_x)为x对情侣没有一对坐在一起的数量
然后答案就可以表示成：(C_n^k*A_n^k*2^k*g_{n-k})
这里的复杂度是(O(T*N))，貌似不错，所以现在问题变成求(p_x)了
第一篇题解是利用这是一个错牌问题，用递推式解决，复杂度为优秀的(O(N))，但是由于询问的复杂度已经是(O(T*N))了，假设我们并不知道这个递推式，我们还能怎么做呢？
考虑暴力容斥：
所有的情况是((2*x)!)，然后一对以上情侣数量为(C_x^1*(2*x-2)!*2*A_x^1)，意义是：我可以在x对中选取一对，其他的(x-1)对是随便做的，然后这对情侣可以交换位置，并且占领(A_x^1)排位置
然后两对以上，三对以上也是差不多的，求出来以后直接容斥就好了，所以整体的柿子长成这样：
[g_x=sum_{i=0}^x2*(-1)^i*C_x^i*(2*x-2*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
", 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;
}