最近补课有种退役的感觉。。。甚至已经想退役了
一眼看上去很像错排。$k$位错排问题可以先$C_n^{n-k}$选出配对的$n-k$个，剩下的$k$个完全错排。
用$f(n)$表示不考虑坐的次序（只考虑谁和谁坐一起），$n$对情侣完全错排的方案数。
然后考虑$n$对情侣至少$i$对的配对的方案数。
$C_n^i$选出配对的$i$对，剩下的$2n-2i$个人任意配对。这里定义$g(n)=\prod\limits_{i=1}^{\frac{n}{2}}(2i-1)$，则有$g(2n-2i)$种方案。
$g(n)$可以预处理，当然可以优雅地百度推导：
套路地容斥一下：
对于任意$n$和$k$，就能先$C_n^k$选出配对的情侣，剩下的$f(n-k)$完全错排，考虑次序，有$n!$种排列，配对的两人之间可以互换，有$2^n$种情况。
答案就是$C_n^kf(n-k)n!2^n$，预处理阶乘、阶乘逆元、$2$的$n$次幂、$2$的$n$次幂的逆元，$O(n^2)$预处理$f$，$O(n)$回答每个询问，足以通过普通版。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define maxn 2005
#define inf 0x3f3f3f3f
const int mod = 998244353;
using namespace std;
inline int read(){
int x=0,y=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return y?-x:x;
}
int pow2[maxn]={1},fac[maxn]={1},inv[maxn],inv2[maxn],f[maxn],n;
int INV(int x){return x==1?1:1ll*(mod-mod/x)*INV(mod%x)%mod;}
inline int C(int m,int n){return 1ll*fac[n]*inv[n-m]%mod*inv[m]%mod;}
inline long long pow_1(int x){return x&1?-1ll:1ll;}
int main(){
for(register int i=1;i<=2000;++i)fac[i]=1ll*fac[i-1]*i%mod,pow2[i]=(pow2[i-1]<<1)%mod;
inv[2000]=INV(fac[2000]),inv2[2000]=INV(pow2[2000]);
for(register int i=1999;~i;--i)inv[i]=1ll*inv[i+1]*(i+1)%mod,inv2[i]=(inv2[i+1]<<1)%mod;
for(register int i=0;i<=2000;f[i]=(f[i]+mod)%mod,++i)
for(register int j=0;j<=i;++j)
(f[i]+=pow_1(j)*C(j,i)%mod*fac[i-j<<1]%mod*inv[i-j]%mod*inv2[i-j]%mod)%=mod;
int t=read();
while(t--){
n=read();
for(register int i=0;i<=n;++i)
printf("%d\n",1ll*C(i,n)%mod*f[n-i]%mod*pow2[n]%mod*fac[n]%mod);
}
}
加强版的看题解表示并不会生成函数也不想递推，咕咕咕
