首先设 $f_i$ 为 $i$ 个点的 DAG 数量，枚举其中的 $i-j$ 个点没有入度，然后剩下 $j$ 个点向它们随意连边，但这样会算重，需要在容斥一下，方程是：

$$ f_i = \sum_{j=1}^{i}{(-1)^{j-1} C_i^j 2^{j(i-j)} f_{i-j}}$$

时间复杂度 $O(n^2)$，可过 $n=5000$。

这个式子看起来就很能卷积，不过这个 $2^{j(i-j)}$ 很烦，可以化一下：

$$j(i-j)=\frac{i^2}{2}-\frac{j^2}{2}-\frac{(i-j)^2}{2}$$

这样就能把 $j$ 和 $i-j$ 分开了。于是：

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

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

设:

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

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

于是：

$$F = A*F +1$$

即：

$$F = \frac{1}{1-A}$$

使用 FFT 卷积，时间复杂度 $O(n\log(n))$，可过 $n=100000$。

做法一：

首先设 $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)$。

显然 $f(S)$ 即为 $m^{\mathsf{连通块个数}}$。

连通块是困难的，要搞容斥系数什么的好像也行，但这个数据范围过不去。

考虑转化一下命题，联通块内颜色相同 $\to$ 边的两点颜色相同。显然两命题等价。此时边就成了两个元素上的限制，表示一种二元关系。不妨设第 $i$ 条边表示的限制为 $p_i$。

则 $f(S)=\mathrm{sum}(\bigcap\limits_{i\in S} p_i)$，其中 $\mathrm{sum}(P)$ 表示限制集为 $P$ 的方案数。

显然只有机器人会处理交集这种限制。此时需要转换视角。发现 $(-1)^{|S|+1}$ 这个东西很像容斥系数，配上 $f(S)$ 化开后 RHS 的式子就更有容斥的感觉了。

写一下答案的式子：

$$\mathrm{ans}=\sum_{\emptyset \neq S\subseteq E} (-1)^{|S|+1}\times f(S)=\sum_{\emptyset \neq S\subseteq E}(-1)^{|S|+1}\times \mathrm{sum}(\bigcap_{i\in S} p_i)=\mathrm{sum}(\bigcup_{i\in E} p_i)$$。

并集是容易处理的。正难则反一下，算总方案减去所有条件都不满足的方案，即 $m^n-m^{\underline n}$。

首先令 $a_n$ 为 $n$ 个奇点的奇树数量，类似的，定义 $b_n$ 为 $n$ 个偶点的偶树数量。

然后令 $A(x)=\sum_{i \ge 0}{a_ix^i}\ ,\ B(x)=\sum_{i \ge 0}{b_ix^i}$.

我们肯定是往根下面连若干个偶树使其成为奇树，或者是往根下面连若干个奇树使其成为偶树。

对于前者，枚举子树的大小，类似背包，可以得到：

$$A(x)=x\prod_{i \ge 1}{(1+x^i+x^{2i}+\dots)^{b_i}}$$

$$=x\prod_{i \ge 1}{(\frac{1}{1-x^i})^{b_i}}$$

乘 $x$ 是因为根本身是一个奇点。

于是：

$$\ln(A(x))=\ln(x)-\sum_{i \ge 1}{b_i\ln(1-x^i)}$$

两边求导：

$$\frac{A'(x)}{A(x)}=\frac{1}{x}+\sum_{i \ge 1}{ib_i\frac{x^{i-1}}{1-x^i}}$$

两边乘 $xA(x)$:

$$xA'(x)=A(x)+A(x)\sum_{i \ge 1}{ib_i\frac{x^i}{1-x^i}}$$

考虑第 $n$ 项系数：

$$na_n=a_n+\sum_{i=1}^{n-1}{a_i\sum_{j=1}^{n-1}{jb_j([x^{n-i}]\frac{x^j}{1-x^j})}}$$

而：

$$\frac{x^j}{1-x^j}=\sum_{i \ge 1}{x^{ij}}=\sum_{i \ge 1}{[j|i]x^i}$$

于是：

$$na_n=a_n+\sum_{i=1}^{n-1}{a_i\sum_{j=1}^{n-1}{jb_j[j|n-i]}}$$

也就是：

$$a_n=\frac{\sum_{i=1}^{n-1}{a_i\sum_{j=1}^{n-1}{jb_j[j|n-i]}}}{n-1}$$

再看后者，类似的，有：

$$B(x)=\prod_{i \ge 1}{(\frac{1}{1-x^i})^{a_i}}-1$$

$-1$ 是因为不存在 $0$ 个偶点的偶树。

类似得到：

$$b_n=\frac{\sum_{i=0}^{n-1}{(b_i+[i=0])\sum_{j=1}^{n}{ja_j[j|n-i]}}}{n}$$

这样就可以使用分治 $NTT$ 解决了，时间复杂度 $O(n\log^2n)$.

拆分成前缀和的形式，$f(x)$ 表示 $[0,x]$ 范围内的解，则答案为 $f(y)-f(x-1)$。

问题等价于将数字转化为 $b$ 进制后 $1$ 的位数为 $k$ 的方案数。

数位 DP 的思想是从高位到低位沿着 $x$ 的上界进行枚举，每次累加这一位取不到上界时的方案数，本题中，这个方案数就是组合数。

时间复杂度为 $O(log^2n)$，瓶颈在于预处理组合数。

细节有：如果 $x$ 满足条件需要在最后累加进去，且一旦有一位上的数大于 $1$ 则代表后面若干位可以任意填 $1$，这时需要跳出循环，选择了 $k$ 个 $1$ 后也应跳出循环，此时后面的若干位应全部填 $0$。

二分图的最大匹配、完美匹配和匈牙利算法