P7490 "Stoi2031" Dandelion Promise (vol.1).

> A promise we made growing up, so clear. I believe in the pinky swear. We agreed to travel together. This is now the only stubbornness you insist on. — "Dandelion Promise".

Qinghe is playing a game. They have $n$ clumps of **dandelions**, where the $i$-th clump has $s_i$ flowers. These **dandelions** have a magical property: given a constant $\sigma \in (0,1)$, from $x$ **dandelions** they split off $\lfloor \sigma x \rfloor$ as one group, and the remaining $x-\lfloor \sigma x \rfloor$ continue splitting, until the split-off group has no **dandelions**, i.e. $\lfloor \sigma x \rfloor=0$. They call this phenomenon **"renxing"** (stubbornness). Now each clump of **dandelions** shows this **"renxing"** phenomenon. The game rules are as follows: starting from Qing, the two players take turns to **travel**. One **travel** means choosing one clump of **dandelions** and blowing away some flowers in the first group of this clump. You must blow away at least one, and at most the size of the first group, i.e. you cannot blow away any **dandelions** outside the first group. When the first group becomes empty, the next group becomes the first group. If a clump has only one group of **dandelions** left, then this clump can no longer be chosen. When no clump can be chosen, the game ends, and the player whose turn it is loses. They want to know: if, on Qing’s first **travel**, she first chooses uniformly at random one clump of **dandelions** that can be operated on, and then uniformly at random chooses the number of flowers to blow away, and after that both players play optimally, what is the value of Qing’s win probability $x \bmod 20190816170251$? The difference from vol.2 is that after part of the **dandelions** are blown away, they **will not** regroup.

The first line contains two positive integers $id,n$, where $id$ denotes the Subtask number. The second line contains $n$ positive integers; the $i$-th one is $s_i$. If $id>3$, the third line contains two positive integers $p,q$ meaning $\sigma=\dfrac{p}{q}$.

Output one integer on one line, which is Qing’s win probability $x \bmod{20190816170251}$.

#### Brief statement: There are $n$ clumps of **dandelions**. The $i$-th clump has $s_i$ flowers. Given a real number $\sigma$, each clump is split into several groups. The $j$-th group has $t_j$ flowers, and satisfies $t_j=\left\lfloor \sigma\left(s_i - \sum\limits_{k=1}^{j-1}t_k\right) \right\rfloor$. When $t_j=0$, no more groups are formed. Two players alternate moves. Each move, a player may choose one clump of **dandelions**, and choose an integer $c \in t_j$, and blow away $c$ flowers from this clump, changing $t_j$ into $t_j-c$, where $j$ is the smallest positive integer such that $t_j \neq 0$ in this clump before the move. You must blow away at least one. If you cannot operate, you lose. Find the value of the first player’s win probability $x \bmod{20190816170251}$, under the process that the first player’s first move is: uniformly choose any operable clump of **dandelions**, then uniformly choose the number of flowers to blow away, and after that both players play optimally. #### Sample explanation: For sample $1$, Qing cannot make any move, so the win probability is $0$. For sample $2$, the initial position is $\{0;1\},\{2,1,1,1,0;2\},\{1,0;2\}$. Qing can choose the $2$-nd clump, and among two possible moves, choose to blow away $2$ flowers, resulting in $\{0;1\},\{1,1,1,0;2\},\{1,0;2\}$. If she chooses the $3$-rd clump, there is no winning strategy. Also, the $1$-st clump cannot be chosen. Therefore the total win probability is $\dfrac{\frac{1}{2}+0}{2}=\dfrac{1}{4}$. #### Constraints: **This problem uses bundled testdata. The score and limits for each Subtask are as follows.** | Subtask No. | $n \le$ | $s_i \le$ | Constraint on $\sigma$ | Score | | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | | $1$ | $3 \times 10^5$ | $10^{10}$ | $\sigma=\dfrac{\sqrt{2}+1}{3}$ | $10$ | | $2$ | $3 \times 10^5$ | $10^{10}$ | $\sigma=\dfrac{\sqrt{3}+1}{5}$ | $10$ | | $3$ | $3 \times 10^5$ | $10^{10}$ | $\sigma=\dfrac{\sqrt{5}-1}{2}$ | $10$ | | $4$ | $100$ | $1$ | None | $3$ | | $5$ | $100$ | $100$ | $\sigma=\dfrac{1}{2}$ | $7$ | | $6$ | $100$ | $10^6$ | None | $13$ | | $7$ | $3 \times 10^5$ | $10^{10}$ | $\sigma \ge \dfrac{1}{2}$ | $47$ | For $100\%$ of the data, $1 \le n \le 3 \times 10^5,1 \le s_i \le 10^{10},1 \le p