Problem J. Just So You Know
时间限制 3500 ms
内存限制 256 MB
Matthew is a wise man and Jesse is his best friend. One day, Jesse gave Mattew an integer sequence $A$ of length $n$ and marked one continuous subsequence $B$ of $A$ privately. Mattew didn't know the sequence $B$ at first, but he can guess out the sequence by conjectures. That is, once he claims some conjecture, Jesse will immediately tell him whether the conjecture is true or not.
Matthew has known the sequence $B$ is an interval selected from the sequence $A$ with equal probability. A wise man is never confused, so Matthew will minimize the expected number of conjectures he needs to figure out the sequence $B$. Could you please determine that expected value? Your answer should be an irreducible fraction $p / q$, which means $p$ and $q$ are coprime.
输入数据
输出数据
For each test case, print in one line the answer as an irreducible fraction $p / q$ if $q \neq 1$ or a simple $p$ otherwise.
样例输入
复制
3
2
1 1
4
1 2 1 1
6
1 1 4 5 1 4
样例输出
样例说明
Here is one possible best solution for the second sample. Claim Conjecture 1 firstly and others consequently following the instructions. Conjecture 1: The number of 1 in B is odd. If true, go to Conjecture 2, else go to Conjecture 3. Conjecture 2: The length of B is 1. If true, B is [1], else go to Conjecture 4. Conjecture 3: The first element of B is 1. If true, go to Conjecture 5, else go to Conjecture 6. Conjecture 4: The length of B is 4. If true, B is [1, 2, 1, 1], else go to Conjecture 7. Conjecture 5: The length of B is 3. If true, B is [1, 2, 1], else B is [1, 1]. Conjecture 6: The length of B is 1. If true, B is [2], else B is [2, 1, 1]. Conjecture 7: The first element of B is 1. If true, B is [1, 2], else B is [2, 1].
$ Mathjax font initiator $