問題一覧 > 通常問題

No.590 Replacement

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 17
作問者 : PulmnPulmn / テスター : ixmelixmel
6 ProblemId : 1645 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2018-07-16 13:23:50

問題文

MAK君とculcul君は以下のような遊びを思いつきました。

この遊びに必要なものは $(1,2,\dots ,N)$ の $2$ つの順列 $A,B$ です。なお、順列 $A,B$ の番号は 1-indexed です。最初、MAK君とculcul君はそれぞれ $1$ 以上 $N$ 以下の自然数を $1$ つ持っており、以下の操作を $2$ 人が持っている自然数の値が一致するまで行います。ただし、何度も操作を繰り返しても、$2$ 人の持っている値が一致せず、遊びが終了しない場合もあります。

・ MAK君が自然数 $i$ を持っていたならば、$i$ は自然数 $A_i$ に変換される。対して、culcul君が自然数 $j$ を持っていたならば、$j$ は自然数 $B_j$ に変換される。
  この $2$ つの変換は同時に行われます。

MAK君とculcul君はこの遊びの性質を知るため、関数 $f(x,y)$ を次のように定義しました。(サンプル $1$ を参考にしてください)
$\begin{eqnarray}\ f(x,y)=\begin{cases} 最初、MAK君が自然数x、culcul君が自然数yを持っていた時、遊びが終了するまでに操作を行った回数 &(遊びが終了する場合) \\
0 &(遊びが終了しない場合) \end{cases}\end{eqnarray}$
MAK君とculcul君は $1\le i,j\le N$ における $f(i,j)$ の総和、すなわち、$\displaystyle \sum_{i=1}^{N}\displaystyle \sum_{j=1}^{N}f(i,j)$ がどのような値になるのか気になりました。ただし、この値は非常に大きくなる場合があるので、$10^9+7=1{,}000{,}000{,}007$ で割った時の余りを出力してください。

入力

$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$ $(1\le i\le N)$
$i\neq j$ ならば $A_i\neq A_j,B_i\neq B_j$

出力

$\displaystyle \sum_{i=1}^{N}\displaystyle \sum_{j=1}^{N}f(i,j)$ を $1{,}000{,}000{,}007$ で割った時の余りを出力してください。最後に改行してください。

サンプル

サンプル1
入力
4
2 1 4 3
3 1 2 4
出力
26

最初、MAK君が $2$ 、culcul君が $1$ を持っていた場合、操作を $2$ 回行った後はMAK君、culcul君ともに $2$ を持っている状態になり、遊びが終了します。そのため、$f(2,1)=2$ になります。
MAK君が $2$ 、culcul君が $4$ を持っていた場合、操作を何回も行っても遊びが終了することはないので、$f(2,4)=0$ になります。
また、MAK君が $1$ 、culcul君が $1$ を持っていた場合、操作を行わずに遊びが終了するので、$f(1,1)=0$ になります。

サンプル2
入力
5
1 2 3 4 5
1 2 3 4 5
出力
0

出力する値が $0$ になる場合もあります。

サンプル3
入力
6
6 2 1 4 3 5
2 4 5 1 3 6
出力
81

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。