問題一覧 > 通常問題

No.590 Replacement

レベル : / AI推定難易度 : 2300 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 22
作問者 : Pulmn / テスター : ixmel
お気に入りにしたユーザー ProblemId : 1645 / 自分の提出
問題文最終更新日: 2026-06-25 19:06:34
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 176 (順位表) の他の問題:

Problem Statement

MAK and culcul came up with the following game.

This game requires $2$ permutations $A,B$ of $(1,2,\dots ,N)$. The permutations $A,B$ are 1-indexed. Initially, MAK and culcul each hold $1$ natural number between $1$ and $N$, inclusive, and they perform the following operation until the values of the natural numbers held by the $2$ of them become equal. Note that there may be cases where, no matter how many times the operation is repeated, the values held by the $2$ of them never become equal and the game does not end.

・ If MAK holds a natural number $i$, then $i$ is converted to the natural number $A_i$. Likewise, if culcul holds a natural number $j$, then $j$ is converted to the natural number $B_j$.
  These $2$ conversions are performed simultaneously.

To learn about the properties of this game, MAK and culcul defined a function $f(x,y)$ as follows. (Refer to Sample $1$.)
$\begin{eqnarray}\ f(x,y)=\begin{cases} 最初、MAK君が自然数x、culcul君が自然数yを持っていた時、遊びが終了するまでに操作を行った回数 &(遊びが終了する場合) \\
0 &(遊びが終了しない場合) \end{cases}\end{eqnarray}$
MAK and culcul became curious about the value of the sum of $f(i,j)$ over $1\le i,j\le N$, that is, $\displaystyle \sum_{i=1}^{N}\displaystyle \sum_{j=1}^{N}f(i,j)$. Since this value can be very large, output the remainder when it is divided by $10^9+7=1{,}000{,}000{,}007$.

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

Output

Output the remainder when $\displaystyle \sum_{i=1}^{N}\displaystyle \sum_{j=1}^{N}f(i,j)$ is divided by $1{,}000{,}000{,}007$. Print a newline at the end.

Sample

Sample 1
Input
4
2 1 4 3
3 1 2 4
Output
26

If MAK initially holds $2$ and culcul initially holds $1$, then after performing the operation $2$ times, both MAK and culcul hold $2$, and the game ends. Therefore, $f(2,1)=2$.
If MAK holds $2$ and culcul holds $4$, the game never ends no matter how many times the operation is performed, so $f(2,4)=0$.
Also, if MAK holds $1$ and culcul holds $1$, the game ends without performing any operation, so $f(1,1)=0$.

Sample 2
Input
5
1 2 3 4 5
1 2 3 4 5
Output
0

The value to output may be $0$.

Sample 3
Input
6
6 2 1 4 3 5
2 4 5 1 3 6
Output
81

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