理性愉悦
打了一发zoj，没有抢到I、J，陷入了B的坑中无法自拔，就成为了爆零选手。
Problem B 给定两个数列A、B，询问有多少个排列σ，满足：A(σ(i)) = σ(B(i))。
以下是嘴巴内容：
Part 1 首先观察式子，发现如果知道了σ(i)，那么就可以由A推出σ(B(i))，把这种关系当做一条边，那么就构成了一张图B。 转化式子为 A(x) = y 。发现这也构成了一张图A。 要满足式子，就要满足图A与图B相同，图A中点的编号就是图B中点的权值，而图B中点就是σ。
Part 2 接下来就要判断图A与图B是否相同，由于每个点只有一条出边，那么这个图就是由一些环加外向树构成的森林，只需要找到图A中的每一棵环加外向树是否存在图B中的一棵环加外向树与其匹配。可以想到对于每一棵环加外向树找一个Hash值，首先考虑树的Hash，这个可以自底向上编号得到Hash值。接下来是环的Hash，这相当于是判断字符串的循环同构，可以用最小表示法搞一搞。最后把Hash值排个序，就可以判断是否有解了。
Part 3 最后是求解的个数。对于树的情况，由于已经知道了子树的Hash值，就可以树形dp求解。对于环的情况，就是每个节点的dp值的乘积再乘上可以匹配的位置数。由于只会和相同的环匹配，再乘个阶乘就可以了。
Part 4 再次声明，以上是嘴巴内容。
写这道题是在__Shi的怂恿下，然后发现这和上面这道题有一定的相似之处。 首先发现t非常大，直接走是不靠谱的，于是想到倍增。需要知道从一个箭头经过2^n个箭头后会停在哪个箭头，且需要的时间。预处理出每个箭头对应的下一个箭头，这可以排序后用线段树搞出来。 然后发现直接倍增也是不可以的，因为t非常大，经过的箭头有可能非常多。 观察可知一个箭头只会对应一个箭头，那么把箭头当做点，这个图就是由一些环加外向树构成的森林。那么先在树上倍增一下，再模环的长度，再在环上倍增一下即可。(据说只要4k就可以完事了，写了8k+真是没有希望了)
ChengChi Zhou 01 December 2014