题解

思路

把 (a_i) 看成从点 (i) 指向点 (a_i) 的有向边。由于每个点出度为一，且没有自环，图由若干基环树组成。可以证明，一个结果 (b) 可实现，当且仅当：

1. 对每个点 (u)，(b_u) 是 (u) 或 (u) 的一个入树儿子；
2. 不会有相邻的两个点同时满足 (b_u=u)；
3. 每个环上至少有一个点的最终占有者不是它的环上前驱。

因此可以用标号组合类的指数生成函数同时统计 (a) 与所有可实现的 (b)。

做法

记 (F) 为一棵有根入树的指数生成函数，(G) 为其中根最终仍由自己占据的生成函数，(D=F-G)。

当根不由自己占据时，要从非空儿子集合中选择一个儿子的标号，故

[ D=xF\exp(F). ]

当根由自己占据时，所有儿子的根都不能仍由自己占据，故

[ G=x\exp(D),\qquad F=D+G. ]

再处理环。记

[ U=x\exp(F),\qquad S=U+D,\qquad T=S(1+G). ]

(U) 对应环上一个点取前驱标号，(D) 对应取非环儿子的标号；若一个环点取自己的标号，就把它与前一个不取自己的点合并，因此得到乘子 (1+G)。

所有环结构由 (-\ln(1-T)) 统计。需要删去每个点都取前驱标号的环 (-\ln(1-U))，还要删去由单个 (D) 形成、等价于 (a_i=i) 的非法一元环。因此一个连通基环树的生成函数为

[ C=-\ln(1-T)+\ln(1-U)-D. ]

不同连通分量构成无序集合，所以总生成函数为

[ A=\exp(C). ]

最终答案为

[ n![x^n]A. ]

子任务 1

枚举全部 ((n-1)^n) 个 (a) 和 (n!) 个攻击顺序，模拟游戏并对每个 (a) 的结果 (b) 去重。

子任务 2

从零级数开始反复代入

[ D=xF\exp F,\qquad F=D+x\exp D. ]

每次代入至少多确定一项系数。做 (n+1) 轮，每轮使用朴素 (O(n^2)) 级数运算，总复杂度 (O(n^3))。

满分算法

按次数从小到大计算系数。若已经得到低于 (i) 次的系数，则

[ D_i=[x^{i-1}]F\exp F,\qquad G_i=[x^{i-1}]\exp D,\qquad F_i=D_i+G_i. ]

对任意常数项为零的级数 (P)，由

[ i[\exp P]i=\sum{j=1}^{i}jP_j[\exp P]_{i-j} ]

可在线计算指数；对常数项为一的 (Q)，由 (Q'=(\ln Q)'Q) 可在线计算对数。每个新系数只需一次卷积前缀，全部运算为 (O(n^2))。

正确性说明

函数图分解唯一，因此可以先统计一棵入树，再统计环，最后用集合构造合并连通分量。方程 (D=xF\exp F) 精确选择根的一个儿子作为最终标号；方程 (G=x\exp D) 精确保证根保留时所有儿子都不保留。环上的三类选择由 (T=S(1+G)) 无重覆盖，减去全取前驱和非法一元环后恰好剩下全部合法连通分量。最后取 (\exp(C)) 正好统计任意个互不相交的连通分量，所以 (n![x^n]A) 就是所求标号结构数量。

复杂度

子任务 1 为 (O((n-1)^n n!,n))；子任务 2 为 (O(n^3))；满分算法时间复杂度 (O(n^2))，空间复杂度 (O(n))。