1783. Brother and Sister
时间限制 1000 ms 内存限制 150 MB
Jin Song and Jin Hui are brother and sister. They go to same university. Jin Song is a member of ICPC training club and Jin Hui is a member of English club.
Today is Jin Hui's $17^{th}$ birthday and it is also the first birthday at university. So, as a good brother, Jin Song prepared an amazing present for his pretty younger sister. But, the mischievous sister went university before he gets up, so he decided to go to the English club and give his birthday present to her.
Jin Hui is a very clever girl, so she thought that her brother will surely come to see her and decided to prepare a funny trick for him. She has n fellows at the English club, and they all agreed with her idea.
First, she asked her fellows to wear same uniform and thick glasses just like as her so that the n+1 girls look like the same. By doing so, Jin Song will get confused and try to find his sister. The trick goes as follow:
Step 1: He randomly and uniformly chooses a girl i who wasn't asked yet and asks to her "Are you my sister?".
Step 2: If the current girl i is Jin Hui(that is, i = 0), she will immediately end this trick.
Else, girl i will say that Jin Hui is the girl pi.
$\bullet$ If $p_i$ = i (hence, she says that she is Jin Hui) or Jin Song had already asked the girl pi, he will notice that they told him a lie and go to Step 1.
$\bullet$Else, he will ask to girl pi and go to Step 2.
Jin Song wants to meet his younger sister as soon as possible, and he wants to know how long it will take to meet his pretty younger sister.
So, your task is to work out the expected value of the number of girls Jin Song will meet before the trick ends (including his younger sister).
Two ways are considered different if and only if the sequence of asked girls is different. In other words, there is at least one number k, the girls he met in k-th turn are different.
Today is Jin Hui's $17^{th}$ birthday and it is also the first birthday at university. So, as a good brother, Jin Song prepared an amazing present for his pretty younger sister. But, the mischievous sister went university before he gets up, so he decided to go to the English club and give his birthday present to her.
Jin Hui is a very clever girl, so she thought that her brother will surely come to see her and decided to prepare a funny trick for him. She has n fellows at the English club, and they all agreed with her idea.
First, she asked her fellows to wear same uniform and thick glasses just like as her so that the n+1 girls look like the same. By doing so, Jin Song will get confused and try to find his sister. The trick goes as follow:
Step 1: He randomly and uniformly chooses a girl i who wasn't asked yet and asks to her "Are you my sister?".
Step 2: If the current girl i is Jin Hui(that is, i = 0), she will immediately end this trick.
Else, girl i will say that Jin Hui is the girl pi.
$\bullet$ If $p_i$ = i (hence, she says that she is Jin Hui) or Jin Song had already asked the girl pi, he will notice that they told him a lie and go to Step 1.
$\bullet$Else, he will ask to girl pi and go to Step 2.
Jin Song wants to meet his younger sister as soon as possible, and he wants to know how long it will take to meet his pretty younger sister.
So, your task is to work out the expected value of the number of girls Jin Song will meet before the trick ends (including his younger sister).
Two ways are considered different if and only if the sequence of asked girls is different. In other words, there is at least one number k, the girls he met in k-th turn are different.
输入数据
The first line of input contains an integer T (1 <= T <= 10) , the number of test cases.
Each test case consists of two lines. The first line of each test case contains an integer n (1 <= n <= 100000), the number of Jin Hui's fellows. All her fellows are numbered from 1 to n. Jin Hui is numbered 0. Next line contains n space-separated integers $p_1, p_2, ..., p_n$ (1 <= $p_i$ <= n), where $p_i$ indicates the number of girl pointed by girl i.
Each test case consists of two lines. The first line of each test case contains an integer n (1 <= n <= 100000), the number of Jin Hui's fellows. All her fellows are numbered from 1 to n. Jin Hui is numbered 0. Next line contains n space-separated integers $p_1, p_2, ..., p_n$ (1 <= $p_i$ <= n), where $p_i$ indicates the number of girl pointed by girl i.
输出数据
For each test case, you can represent the expected value in a irreducible fraction of p/q (that is, p and q are co-primes). Then, you must output a single integer $pq^{-1}$ mod ($10^9$+7) in one line.
样例说明
If you choose the first girl of trick, then the trick is uniquely determined.
One way is to choose his sister first, and others are to choose 1, 2, 3.
If he chooses his sister first, the trick ends in one turn.
If he chooses 1 first, then he must follow in order of 1, 2, 3.
Then he will notice that they told him a lie and directly go to his sister.
So the trick ends in four turns following the sequence of {1, 2, 3, 0}.
In case of choosing 2 or 3 first is very similar ({2, 3, 1, 0}, {3, 1, 2, 0}).
Each case occurs with the same probability of 1 / 4.
So the answer is
(1 + 4 + 4 + 4) * 4^(-1) mod (10^9+7) = 250000005
提交
请先 登录
Source
2017 Multi-University Training Contest - Team 10