两道好题做了一上午，可见我的组合数学有多差，只会暴力拆式子，于是加强版只好看题解了。。总结一下于是有了这篇题解。
普通版
最 (naive) 的想法就是：钦定 (k) 对情侣，给他们安排座位，两个人可以互换位置，其余人是一个变相的错排：(C_n^kA_n^k2^kf(n-k)) ，(f(k)) 表示 (k) 对人坐 (2k) 个位置不配对的情况数。我发现这个 (f(k)) 我根本不会求就放弃了这个思路。
之前没见过二项式反演，所以没什么感觉。现在一上来就设俩式子：
(f(k)) 表示至少 (k) 对情侣和睦
(g(k)) 表示恰好 (k) 对情侣和睦
我们要求的是 (g(i),i=0,1,cdots,n)
显然 (f(k)=sum_{i=k}^{n}inom{n}{k}g(i)) 。
由二项式反演得 (g(k)=sum_{i=k}^{n}(-1)^{i-k}inom{n}{k}f(i))
考虑把 (f(k)) 换一种表示（之前设这两个式子的原因其实是因为看到 (f(i)) 好算）：
首先钦定 (k) 对和睦的情侣，然后给他们挑 (k) 个位置，每一对情侣可以互换位置，其余人随便排（这里是“至少”的体现，有可能大于 (k) ，但是不可能小于 (k)）
把上面的文字写成式子就是 (f(k)=C_n^kA_n^k2^k(2n-2k)!)
(f) 可以一遍 (O(n)) 扫出来，但是 (g) 呢？它要 (O(n^2)) 。怎么办？想了一会感觉没啥别的想法就开始大力拆式子：
(sum) 后面那个东西对于每一个 (n-k) 是固定的，只有 (O(n)) 种，可以 (O(n^2)) 暴力预处理
然后就做完了。
//Orz cyn2006
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double db;
#define mkp(x,y) make_pair(x,y)
#define fi first
#define se second
#define pb(x) push_back(x)
inline int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=0;ch=getchar();}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return f?x:-x;
}
#define N 2005
#define mod 998244353
int n,f[N],g[N],fac[N],ifc[N],pw2[N];
int qpow(int n,int k){int res=1;for(;k;k>>=1,n=1ll*n*n%mod)if(k&1)res=1ll*n*res%mod;return res;}
void init(){
int up=2000;
fac[0]=1,pw2[0]=1;
for(int i=1;i<=up;++i)fac[i]=1ll*fac[i-1]*i%mod,pw2[i]=(pw2[i-1]<<1)%mod;
ifc[up]=qpow(fac[up],mod-2);
for(int i=up-1;i>=0;--i)ifc[i]=1ll*ifc[i+1]*(i+1)%mod;
up=1000;
for(int i=0;i<=up;++i){
for(int j=0;j<=i;++j)
f[i]=(f[i]+1ll*(j&1?-1:1)*pw2[j]*ifc[j]%mod*fac[2*i-2*j]%mod*ifc[i-j]%mod*ifc[i-j]%mod+mod)%mod;
}
}
int A(int n,int m){return 1ll*fac[n]*ifc[n-m]%mod;}
int C(int n,int m){return 1ll*fac[n]*ifc[n-m]%mod*ifc[m]%mod;}
signed main(){
init();
for(int T=read();T;--T){
n=read();
for(int i=0;i<=n;++i)printf("%lld
",1ll*pw2[i]*fac[n]%mod*fac[n]%mod*ifc[i]%mod*f[n-i]%mod);
}
}
加强版
原本以为就是简单版加一个多项式就好了的，那个式子 (sum) 后面那部分显然可以 (NTT) 卷起来。
当我看到 (nle 5 imes10^6) 之后意识到事情有些不对劲。
看了题解发现神仙出题人把普通版里最开始写的那个式子的 (f) 推出来了！！！
技不如人啊，我被吊打了/kk
(C_n^kA_n^k2^kf(n-k))
考虑怎么求 (f)
考虑分类讨论一下：
选两个人，ta们不是配偶，这样有 (2k*(2k-2)) 种情况，然后考虑ta们配偶的情况
- 如果强制让ta们配对，相当于在剩下 (k-1) 个位置选一个给ta们，同时ta们还可以交换位置，是 (2(k-1)f(k-2))
- 如果强制让ta们分开，相当于少了俩人，剩下的人又是一个错排，为 (f(k-1))
完全不知道第二种情况是怎么看出来的，出题人太神仙了。
边界 (f(0)=1,f(1)=0)
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double db;
#define mkp(x,y) make_pair(x,y)
#define fi first
#define se second
#define pb(x) push_back(x)
inline int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=0;ch=getchar();}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return f?x:-x;
}
#define mod 998244353
#define N 5000005
int T,n,k;
int pw2[N],fac[N],ifc[N],f[N];
int qpow(int n,int k){int res=1;for(;k;k>>=1,n=1ll*n*n%mod)if(k&1)res=1ll*n*res%mod;return res;}
void init(){
int up=N-5;
pw2[0]=fac[0]=1;
for(int i=1;i<=up;++i)fac[i]=1ll*fac[i-1]*i%mod,pw2[i]=(pw2[i-1]<<1)%mod;
ifc[up]=qpow(fac[up],mod-2);
for(int i=up-1;i>=0;--i)ifc[i]=1ll*ifc[i+1]*(i+1)%mod;
f[0]=1,f[1]=0;
for(int i=2;i<=up;++i)f[i]=4ll*i*(i-1)%mod*(2ll*(i-1)*f[i-2]%mod+f[i-1])%mod;
}
int A(int n,int m){return 1ll*fac[n]*ifc[n-m]%mod;}
int C(int n,int m){return 1ll*fac[n]*ifc[n-m]%mod*ifc[m]%mod;}
signed main(){
init();
for(int T=read();T;--T)
n=read(),k=read(),printf("%lld
",1ll*A(n,k)*C(n,k)%mod*pw2[k]%mod*f[n-k]%mod);
}