yukicoder-590

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#!html
<script type="text/x-mathjax-config">MathJax.Hub.Config({tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}});</script>
<script type="text/javascript" async src="http://10.71.10.90/sfiction/tool/MathJax/MathJax-master/MathJax.js?config=TeX-MML-AM_CHTML"></script>
<style>
.input, pre {
    display: block;
    padding: 9.5px;
    margin: 0 0 10px;
    font-size: 13px;
    line-height: 1.42857143;
    color: #333;
    word-break: break-all;
    word-wrap: break-word;
    background-color: #f5f5f5;
    border: 1px solid #ccc;
    border-radius: 4px;
}
</style>
}}}

== [https://yukicoder.me/problems/no/590 No.590 Replacement] ==

=== Description ===

{{{
#!html
<p>有两个$\{1,2,\dots,N\}$的排列$A$和$B$，他们的下标从$1$开始。MAK和culcul开始玩游戏，一开始他们手中分别有一个$1$到$N$的整数，然后按照进行下面的操作，直到两个人手上的数变成一样：如果MAK手上拿着$i$，那么$i$变为$A_i$；同时，如果culcul手上拿着$j$，那么$j$变成$B_j$。</p>

<p>令$f(x,y)$表示一开始MAK手上拿着$x$，culcul手上拿着$y$，游戏结束需要的操作次数。如果游戏不能结束，那么$f(x,y)=0$。</p>

<p>求出$\sum\limits_{i=1}^{N}\sum\limits_{j=1}^{N}f(i,j)$对$10^9+7$取模的值。</p>
}}}

=== Input ===

{{{
#!html
<p class="input">
$N$<br>
$A_1$ $A_2$ $\dots$ $A_N$<br>
$B_1$ $B_2$ $\dots$ $B_N$<br>
</p>

<p>$1 \le N \le 10^5, 1 \le A_i, B_i \le N$。对于$i \ne j$，$A_i \ne A_j, B_i \ne B_j$。</p>
}}}

=== Output ===

{{{
#!html
<p>输出$\sum\limits_{i=1}^{N}\sum\limits_{j=1}^{N}f(i,j)$对$10^9+7$取模的值</p>
}}}

=== Sample ===

==== Sample 1 ====
输入
{{{
#!html
<pre>
4
2 1 4 3
3 1 2 4
</pre>
}}}
输出
{{{
#!html
<pre>
26
</pre>
}}}

==== Sample 2 ====
输入
{{{
#!html
<pre>
5
1 2 3 4 5
1 2 3 4 5
</pre>
}}}
输出
{{{
#!html
<pre>
0
</pre>
}}}

==== Sample 3 ====
输入
{{{
#!html
<pre>
6
6 2 1 4 3 5
2 4 5 1 3 6
</pre>
}}}
输出
{{{
#!html
<pre>
81
</pre>
}}}

No.590 Replacement

Description

有两个$\{1,2,\dots,N\}$的排列$A$和$B$，他们的下标从$1$开始。MAK和culcul开始玩游戏，一开始他们手中分别有一个$1$到$N$的整数，然后按照进行下面的操作，直到两个人手上的数变成一样：如果MAK手上拿着$i$，那么$i$变为$A_i$；同时，如果culcul手上拿着$j$，那么$j$变成$B_j$。

令$f(x,y)$表示一开始MAK手上拿着$x$，culcul手上拿着$y$，游戏结束需要的操作次数。如果游戏不能结束，那么$f(x,y)=0$。

求出$\sum\limits_{i=1}^{N}\sum\limits_{j=1}^{N}f(i,j)$对$10^9+7$取模的值。

Input

$N$
$A_1$ $A_2$ $\dots$ $A_N$
$B_1$ $B_2$ $\dots$ $B_N$

$1 \le N \le 10^5, 1 \le A_i, B_i \le N$。对于$i \ne j$，$A_i \ne A_j, B_i \ne B_j$。

Output

输出$\sum\limits_{i=1}^{N}\sum\limits_{j=1}^{N}f(i,j)$对$10^9+7$取模的值

Sample

Sample 1

输入

42 1 4 33 1 2 4

输出

26

Sample 2

输入

51 2 3 4 51 2 3 4 5

输出

0

Sample 3

输入

66 2 1 4 3 52 4 5 1 3 6

输出

81