P8967 Pursuit of Dream | Pursuit of Dream

“When you meet someone or something you truly like, never give up.” “Keep pursuing…” “Because even if the chance of success is slim, it is still possible.” Someone once said this to me. It flashed through my mind for a moment, and then I forgot it together with other useless encouragement. Now I want to recall it, but I still cannot remember who it was. Since you have managed to come to this world once, do not leave any regrets. Raindrops falling from the eaves tapped the stone bricks in a steady rhythm, yet in the rain that night, everything also fell silent. Drying tears against the wind, the pain that cannot be spoken is hidden deeper and deeper, rotting in the stomach. Yet we do not know that both sides already understand it, so we cannot give birth to a good ending; only the drama of lovers hurting each other keeps being played. --- I saw the starry wilderness falling into your eyes, and from then on I was willing to sink in that dreamlike low pressure, like the bottom of the sea. The radiance of a three-thousand-foot starry sky cannot reflect that person’s silhouette. In the brilliance, only a god is left longing for an old friend; but that person has scattered into a perhaps shattered sea of stars, making the god search for a lifetime. Those desires that cannot be fulfilled will grow barren day by day. Then the dream will lose its vitality, darkness will spread from the cracks, and tears will have nowhere to be buried. The god told me so, but I do not believe it, because there is no time left for me to daydream. The god also said that after a person dies, the relatives who left earlier will wait for you in another world. In fact, I also think that this must be another world.

In an $n$-dimensional space, there is a dream. This dream is located at $(d_1, d_2, \ldots, d_n)$. You start from $(0, 0, \ldots, 0)$ and begin the journey to seek the dream. Your steps are gentle: each step can only move one unit length. You do not know where your dream is, so you can only randomly choose one of the $n$ positive directions and take one step in that direction. That is, uniformly randomly choose a positive integer $h$ in $[1, n]$, and then increase your coordinate in the $h$-th dimension by $1$. However, things may go wrong. During each step you take, with probability $p = \sum_{i = 1}^k p_i$, you will scatter into the sky and start a new journey. You will restart the journey at one of $k$ locations. The coordinates of the $i$-th location are $(a_{i,1}, a_{i,2}, \ldots, a_{i,n})$, and the probability of restarting from there is $p_i$. Then, in expectation, how many more steps do you need to reach this dream?

The first line contains two positive integers $n, k$. The second line contains $n$ non-negative integers $d_1, d_2, \ldots, d_n$. The next $k$ lines: the $i$-th line contains $n + 1$ integers $a_{i, 1}, a_{i, 2}, \ldots, a_{i, n}, x_i$. The last integer $x_i$ in each line indicates $p_i = x_i \times 10^{-8}$. The input $x_i$ guarantees that $p_i > 0$ and $p < 1$. It is guaranteed that each $x_i$ is generated uniformly at random among all possible combinations.

One line containing one integer, representing the result modulo $998244353$. If you do not know how to take a real number modulo: you may note that the answer is guaranteed to be finite and is a rational number. Let its reduced fraction form be $\frac{p}{q}$. If there exists an integer $x$ such that $x \cdot q \equiv p \pmod{998244353}$ and $0 \le x < 998244353$, then you only need to output the value of $x$. Since it is guaranteed that $x_i$ are generated randomly, it can be argued that with probability close to $1$ the answer exists in the modular sense. In fact, for this problem, an algorithm that outputs the correct answer with reasonably high probability when $x_i$ are still unknown is sufficient to pass. Our intention is not to test complicated handling of rationals under modular arithmetic.

**Sample Explanation \#1** This is one possible way for you to pursue the dream: You start from $(0,0)$, take one step to $(1,0)$, then one step to $(2,0)$, then one step to $(3,0)$. But on the way you scatter into the sky and restart the journey from $(0,0)$. Then continue from $(0,0)$, take one step to $(0,1)$, then one step to $(1,1)$. But on the way you scatter into the sky and restart the journey from $(0,0)$. Next, start from $(0,0)$, take one step to $(1,0)$, then one step to $(1,1)$, and you find your dream. In this case, you need $7$ steps to reach this dream. The probability of this happening is $4^{-7}$. --- **Sample Explanation \#2** The answer is $\frac{505}{24} \approx 21.041667$. It is not hard to verify that $291154624 \times 24 \equiv 505 \pmod{998244353}$, so you should output $291154624$. --- **Sample Explanation \#3** The answer is $\frac{1399505}{21519} \approx 65.035782$. --- **Constraints** **This problem uses bundled testdata and subtask dependencies.** | Subtask ID | Special Constraints | Score | | :----------: | :----------: | :----------: | | 1 | $n=1$, $k=1$ | 11 | | 2 | $n=1$ | 12 | | 3 | $k=1$ | 12 | | 4 | $n=2$, $1 \le d_1 \cdot d_2 \le 200$ | 13 | | 5 | $k \le 200$ | 22 | | 6 | No special constraints | 30 | For $100\%$ of the data: - $1 \le n \le 100$, $1 \le k \le 10000$. - $d_i \ge 0$, $\sum_i d_i \le 10^7$. - $0 \le a_{i, j} \le {10}^7$. - $x_i \ge 1$, $\sum_i x_i < {10}^8$. This guarantees $p_i > 0$ and $p < 1$. - It is guaranteed that there exists an $i \in [1, k]$ such that for every $j \in [1, n]$, we have $a_{i,j} \le d_j$. - It is guaranteed that each $(a_{i, 1}, a_{i, 2}, \ldots, a_{i, n})$ is distinct as a point in space. - It is guaranteed that each $x_i$ is generated uniformly at random among all possible combinations. --- **Hint** Since it is guaranteed that $x_i$ are generated randomly, it can be argued that with probability close to $1$ the answer exists in the modular sense. In fact, for this problem, an algorithm that outputs the correct answer with reasonably high probability when $x_i$ are still unknown is sufficient to pass. Our intention is not to test complicated handling of rationals under modular arithmetic. The $x_i$ in the samples are not randomly generated; they are only for understanding the statement. Translated by ChatGPT 5