开赛的时候看了一眼，时限 7s 模数还是 就以为是 poly 没碰，结果被 B 杀了 1h，最后 20min 才有时间读题（因为看到了最后一个样例答案是个 ，像若干个数的乘积），结果发现这个是唐题，蚌埠住了。
首先显然可以对每个点求出（不考虑其他点的限制时）他能呆的位置集合，因为每次操作是交换相邻两个，所以每个点的移动都是连续的，所以上述位置集合是一个区间。
然后发现一个很显然的结论是，上述区间两两要么包含要么不交。证明也是显然的，考虑一个树上的节点 ， 子树中的节点在 序列中构成了若干极长段。若有一个 满足 ，则 能呆的位置集合就是 所在的那个极长段。对于一个节点 ，对应的极长段两两不交，所以对于所有 的极长段们构成的区间集合也有两两包含或不交。
但是实际上一个点移动到某个位置的时候可能会影响其他点，比如说一个点根本无法移动，那么其他点移动的时候也无法跨过该点。
考虑推广该限制，即建出区间的树形结构后，若一个节点能呆的位置集合恰好等于其子树大小，那么其他节点无法跨过它的位置集合。必要性证明考虑如果要经过该位置集合，一定会把一个子树内的点从该位置集合中换出来。而子树内的点的位置集合都被该位置集合包含，所以这样一定不合法。
所以我们将能呆的位置集合按照上述过程收缩到不包含任何一个实际上不合法的位置，即为实际能到的位置集合。注意到后者也是一个区间，且同样满足两两要么包含要么不交的限制，所以答案确实是类似这样的。注意题目要求的是求本质不同的序列个数，所以有些时候可能要除掉一些东西。
上述过程都可以用数据结构简单维护，具体见代码。