做法一：

首先设 $f_i$ 表示至少 $i$ 对和睦的方案，$g_i$ 表示恰好 $i$ 对和睦的方案。

显然有：

$$f_i=\sum_{j=i}^{n}{C^i_jg_j}$$

根据二项式反演，有：

$$g_i=\sum_{j=i}^{n}{(-1)^{j-i}C^i_jf_j}$$

而我们还有：

$$f_i=C^i_nA^i_n2^i(2n-2i)!$$

于是：

$$g_i=\sum_{j=i}^{n}{(-1)^{j-i}C^i_jC^j_nA^j_n2^j(2n-2j)!}$$

$$=\frac{n!^2}{i!}\sum_{j=i}^{n}{\frac{(-1)^{j-i}2^j}{(j-i)!(n-j)!}}$$

显然可以卷积，于是时间复杂度 $O(Tn\log n)$.

本题还有个加强版，每次询问只需要求一组 $(n,k)$ 的答案，但 $T \le 2e5,n \le 5e6$。

做法二：

发现实际要求的是错排的方案数，记 $F_n$ 表示 $n$ 对情侣的错排方案数，于是：

$$ans(n,k)=C^k_nA^k_n2^kF_{n-k}=(C^k_n)^2k!2^kF_{n-k}$$

而显然：

$$\sum_{k=0}^{n}{ans(n,k)}=\sum_{k=0}^{n}{(C^k_n)^2k!2^kF_{n-k}}=(2n)!$$

化成卷积形式：

$$\sum_{k=0}^{n}{\frac{2^k}{k!}\frac{F_{n-k}}{(n-k)!^2}}=\frac{(2n)!}{n!^2}$$

于是我们设:

$$A(x)=\sum_{i \ge 0}{\frac{2^i}{i!}x^i}$$

有：

$$A(x)=\sum_{i \ge 0}{\frac{(2x)^i}{i!}}=e^{2x}$$

再设：

$$F(x)=\sum_{i \ge 0}{\frac{F_i}{i!^2}x^i}$$

再设：

$$B(x)=\sum_{i \ge 0}{\frac{(2i)!}{i!^2}x^i}$$

根据广义二项式定理，有：

$$B(x)=(1-4x)^{-\frac{1}{2}}$$

再代入上边的卷积式得：

$$A \cdot F=B$$

也就是：

$$F(x)=\frac{e^{-2x}}{(1-4x)^{\frac{1}{2}}}$$

求个导：

$$F'(x)=\frac{8xe^{-2x}}{(1-4x)^{\frac{3}{2}}}=\frac{8x}{1-4x}F(x)$$

于是得到：

$$F'(x)=4xF'(x)+8xF(x)$$

观察系数：

$$F_{n+1}=4n(n+1)F_n+8n^2(n+1)F_{n-1}$$

终于得到了递推式，可以 $O(n+T)$ 解决加强版。本题同样也可 $O(n+Tn)$。