A. gift

考虑把需要 $swap$ 的关系表示在图上。于是形成若干个环。

容易发现交换的次数就是点数减环数。

所以原题转化为环的计数问题。

考虑把已有的每个连通块的部分表示出来。

容易发现对于一条链我们并不关注中间是谁，只关注链首和链尾的状态，于是可以转化为五种形态。

• 如果已经出现了环，那么直接统计答案即可。
• 如果起点为 $0$，终点为 $x$，可以缩掉中间的部分，直接表示为 $0 \rightarrow x$
• 如果起点为 $x$，终点为 $0$，可以表示为 $x \rightarrow 0$
• 如果起点为 $0$，终点为 $0$，可以表示为 $0 \rightarrow 0$
• 如果起点为 $x$，终点为 $y$，可以表示为 $x \rightarrow y$

最后一种情况并不关键，如果存在一个 $x \rightarrow y$，那么说明 $x,y$ 都只出现了一次。

所以在 $0 \rightarrow 0$ 里面 $x,y$ 都出现过。

如果我们不考虑 $y$，只用 $x$ 去组合，最终的每种方案可以直接用 $x \rightarrow y$ 这一条链去替换 $x$ 一个点，显然方案是一一对应的。

所以只需要考虑中间三种情况。

发现 $0 \rightarrow x$ 和 $x \rightarrow 0$ 之间的关系并不大。

二者如果连接，只能通过 $0 \rightarrow 0$ 作为媒介。

对于二者与 $0 \rightarrow 0$ 连接，发现连接之后仍然可以表示为 $0 \rightarrow 0$，所以 $0 \rightarrow 0$的数目也是不改变的。

所以可以认为，二者内部可以直接形成环，或者加入 $0 \rightarrow 0$的队伍，最终形成环。

容易发现 $0 \rightarrow 0$ 的情况比较简单，方案数就是简单的环排列。

对于 $0 \rightarrow x$ 或 $x \rightarrow 0$，考虑如何计算出每个环数目对应的方案数。

设 $f_i$ 表示恰好 $i$ 个环的方案数， $g_i$ 表示至少 $i$ 个环的方案数。

那么有 $g_i=\sum \limits_{j=i}^n\binom{n}{j} \begin{bmatrix}i\\j\end{bmatrix} A(n+m-j,n-j)$。

表示钦定其中的 $j$ 个形成 $i$ 个环，剩下的 $n-j$ 个则随意选择，简单的二项式反演即可容斥出 $f_i$。

另外一种求法是 $f_i=\sum \limits_{j=i}^n\binom{n}{j} \begin{bmatrix}i\\j\end{bmatrix} \frac{(n+m-j-1)!}{(m-1)!}$。

这个式子类似插板法，其中的 $m-1$ 表示板数，因为板是没有区别的所以要除掉一个阶乘。

有了 $f$ 数组可以直接卷积得到答案。

 

B. girls

容易发现计算全部三元组-非法三元组就完事了。

通过交集总和简单容斥出并集总和，问题就解决了。

 

C. string

广义后缀自动机，同时用不换根 LCT 维护 $endpos$ 集合大小。

只要实现简单的链加操作就好了。

因为询问每个串，所以考虑对每个节点维护 $n$ 种 $endpos$ 集合大小。