当前你的浏览器版本过低，网站已在兼容模式下运行，兼容模式仅提供最小功能支持，网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。
6174：Brother and Sister
题目描述
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.
输入样例
1 3 2 3 1
输出样例
250000005
提示
There are 4 ways to choose the first girl. 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
来自杭电HDUOJ的附加信息
| Recommend | liuyiding |
最后修改于 2020-10-25T23:29:02+00:00 由爬虫自动更新
共提交 0 次
通过率 --%
| 时间上限 | 内存上限 |
| 2000/1000MS(Java/Others) | 153428/153428K(Java/Others) |
登陆或注册以提交代码