P7491 「Stoi2031」Dandelion Promise (vol.2)

> A promise we made growing up, so clear. I believe in the pinky swear. We agreed to travel together. It is your only stubborn insistence now. —— "Dandelion Promise"

Qinghe is playing a game. They have $n$ bunches of **dandelions**, and the $i$-th bunch has $s_i$ flowers. These **dandelions** have a magical property: for a given constant $\sigma \in (0,1)$, for $x$ flowers, $\lfloor \sigma x \rfloor$ flowers are split off as one group, and the remaining $x-\lfloor \sigma x \rfloor$ flowers continue to be split in the same way, until the split-off group contains no **dandelions**, i.e. $\lfloor \sigma x \rfloor=0$. They call this phenomenon **"renxing"** (stubbornness). Now each bunch of **dandelions** has this **"renxing"** property. The rules are as follows: Starting from Qing, the two players take turns to make a **travel** move. One **travel** move means choosing one bunch of **dandelions** and blowing away some flowers from the first group of that bunch. You must blow away at least one flower, and at most the size of the first group; that is, 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 bunch has only one group of **dandelions** left, then this bunch can no longer be chosen. When no bunch 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 chooses uniformly at random one bunch 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 winning probability $x \bmod{20190816170251}$? The difference from vol.1 is that after a bunch of **dandelions** is partially blown away, it **will** be regrouped.

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 per line, representing Qing’s winning probability $x \bmod{20190816170251}$.

#### Brief statement: There are $n$ bunches of **dandelions**; the $i$-th bunch has $s_i$ flowers. Given a real number $\sigma$, two players move alternately. Each move can choose one bunch of **dandelions**, and choose an integer $c \in (0,\sigma s]$, then blow away $c$ flowers from that bunch, where $s$ is the number of flowers in that bunch before the move. You must blow away at least one flower. If a player cannot move, that player loses. Find the value of the first player’s winning probability $x \bmod{20190816170251}$, under the process where on the first move the first player uniformly at random chooses any operable bunch of **dandelions** and then uniformly at random chooses the number of flowers to blow away, and afterwards both players use optimal strategies. #### Sample explanation: For sample $1$, Qing cannot make any move, so the winning probability is $0$. For sample $2$, Qing can choose the $2$-nd bunch and, among two possible moves, choose to blow away $2$ flowers to become $1,5,3$; or choose the $3$-rd bunch and choose the only possible move to become $1,7,2$. The $1$-st bunch cannot be chosen. The overall winning probability is $\dfrac{\frac{1}{2}+1}{2}=\dfrac{3}{4}$. #### Constraints: **This problem uses bundled testdata. The score and limits of each Subtask are as follows.** | Subtask No. | $n \le$ | $s_i \le$ | $\sigma$ restriction | 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