前言

发现这个题解的组合意义好像有问题，解释不了放弃的情况，但是对面作者好像是 $10$ 级钩大蛇。

似乎向上面的题解一样理解还需要考虑更多，反正我看不懂，那个题解也没说。

而且第 $i$ 个人有 $n-i+1$ 个位置就是错的。

为 $\text{uid}=114514$ 大佬的“严谨”的题解添加了一些证明并加入了一下自己的理解。

思路

发现换来换去的很麻烦，如果按照操作去考虑那么很难去重，直接从答案入手判断合法。

设第 $i$ 个点最后到达了 $p_i$，那么把 $i$ 向 $p_i$ 连边，需要注意是考虑结果而不是过程，所以即使 $t_i=1$ 也有可能 $i$ 的度为 $2$。

手玩发现一个性质，一些交换是合法的当且仅当一个环内最多存在 $2$ 个 $t_i=1$ 的点。

下面考虑证明这个性质。

考虑通过构造的思想证明。

因为交换的位置并没有限制，所以输入的顺序对答案没有影响，对答案影响的只有 $t_i=1$ 和 $t_i=2$ 的个数，我们假设分别有 $x,y$ 个。

不妨假设 $1$ 到 $x$ 都是 $t_i=2$ 的人，而 $x+1$ 到 $n$ 都是 $t_i=1$ 的人。

不妨先把 $1$ 和 $x+1$ 合并到一起，操作最少的显然就是让他们两人交换手中的球，经过操作 $1$ 就只能交换 $1$ 次了，而 $p_{x+1}=1$ 就已经确定了。

如果需要让这个环内添加更多的元素，那么显然需要操作 $1$ 号跟别人交换。

如果 $1$ 号与 $x+2$ 这样只能交换一次的人交换，那么显然 $p_1=x+2$ 和 $p_{x+2}=x+1$ 都已经确定了，所以最后形成的环就是 $1\to x+2\to x+1\to 1$，只含有 $2$ 个 $t_i=1$ 的节点。

如果 $1$ 号与 $2$ 号这样可以交换两次的人交换，那么 $p_1=2$ 就确定了，而 $2$ 号又只能操作一次，场面与 $1$ 号操作的情况就一样了，所以继续回到上面的情况讨论。

现在回到最开始，如果 $1,2$ 这样本来就可以还两次的点那么他们就相当于合并成为了一个 $t_i=2$ 的点，对上面的证明没有影响。

感性理解一下上面的操作显然可以通过“合并”操作搞出所有的操作，所以综上所述命题得证。

形成的完整的图不可能有链，认为形成的链的两端分别是 $t_i=1$ 的思路是错误的！！！

所以现在问题转化成为了满足上面要求的本质不同的基环树的计数问题。

因为上面的命题对 $t_i=2$ 的点并没有要求，那么那我们把全部 $y$ 个 $t_i=2$ 的点 $p$ 随便乱排显然都会有合法的答案。

下面先只考虑 $t_i=2$ 的贡献。

考虑分析一下原因，这样只操作 $t_i=2$ 的情况会形成一下的图：

• $t_i=2$ 的点自己成为一个大环。
• 一堆 $t_i=2$ 的点形成一条链最终连接一个 $t_i=1$ 的节点。
• 一堆没有边的 $t_i=1$ 的节点。

如果只关注有 $t_i=1$ 的点，那么上述的第 $2$ 种情况就可以缩为一个 $t_i=1$ 的节点。

接下来的操作就只与 $t_i=1$ 的点有关了，之前的操作都和后面的操作独立。

容易发现第一种操作的方案数为 $\large{A^y_n}$，根据乘法原理答案就是前后两个方案相乘。

下面开始考虑 $t_i=1$ 的贡献。

现在问题就转化成了将 $x$ 个不同的元素分成若干组，每一组的元素个数不大于 $2$ 的本质不同的分法。

设 $f_i$ 表示已经处理了 $i$ 个元素的方案数，那么有转移方程：

$f_{i}=f_{i-1}+f_{i-2}\times (i-1)$

• $f_{i-1}$ 表示自己单独成为一组，所以直接把前面的方案加进来就行了。
• $f_{i-2}\times (i-1)$ 表示在前面的 $i-1$ 个元素中选择 $1$ 个元素与 $i$ 放到一个组里，剩下 $i-2$ 个元素随便分组的方案数。

所以最终的答案就是 $\large{A_n^y}\normalsize \times f_{x}$。

代码

Submission #289112469 - Codeforces