Function

题目链接

题意

已知一个$n$的全排列$a$，和一个$m$的全排列$b$，现在问你有多少种不同的映射$f$使得满足以下条件：

$$f(i)=b_{f(a_{i})}, 0 \leq i < n-1$$

答案对$1000000007$取模。

思路

假设对于我们现在已有的一个$f$映射，存在这样的关系：

$$f(i)=b_{f(a_{i})}$$ $$f(a_{i})=b_{f(a_{a_{i}})} ...$$ $$f(i)=b_{b_{b_{...b_{t}}}}.$$

则我们可以得到一个与$i$有关的闭合环，设$0$到$n-1$中有$w$个这样的环，则这些环之间是不会相互影响的，我们可以分别算出每个环有多少种合法的映射。

对于一个有$x$个数字的环，我们有多少种合法的映射呢？观察以下可以发现，只要确定其中一个位置映射的数字，就可以确定整个环中所有数字的映射，为了使环绕回$i$位置时与原来我们假设的数字不冲突。可以先在$b$数列中求出每个位置循环大小。

$$设为sz_{b}(i), a中环大小sz_{a}(i)，则a中包含位置i的环合法映射数量为$$ $$\sum_{j=0}^{j < m} [sz_{b}(j)|sz_{a}(i)]$$

实际上我们只需要统计数量，所以不需要把每个位置是多少记录下来，只需要处理$a$时记录对应的$sz_{b}(j)$的数量即可。