No.2305 [Cherry 5th Tune N] Until That Day...
タグ : / 解いたユーザー数 13
作問者 : 👑
Kazun
/ テスター :
Story
"Even if we say goodbye here, we'll surely meet again somewhere, won't we?"
Problem Statement
There is a rooted tree with $(N+1)$ vertices. The $(N+1)$ vertices are numbered $0,1,2,\dots,N$. The root is vertex $0$, and the parent of vertex $i~(1 \leq i \leq N)$ is vertex $P_i~(0 \leq P_i \lt i)$.
Cherry is initially at vertex $0$.
Cherry moves between vertices some number of times according to the following rules.
- If the vertex Cherry is at is not a leaf: she moves to one of the children of that vertex. The destination is chosen with probability proportional to $W_i$.
- Formally, when the children of that vertex are $u_1, u_2, \dots, u_l$, the probability that $u_i$ is chosen as the next destination is $\dfrac{W_{u_i}}{W_{u_1}+W_{u_2}+\dots+W_{u_l}}$.
- If the vertex Cherry is at is a leaf: she moves to the root (vertex $0$).
Answer the following $Q$ queries $q~(1 \leq q \leq Q)$.
- Query $q$ : Let $E$ be the expected number of times vertex $A_q$ is chosen as the destination when Cherry performs the above move $K_q$ times. Find $E \pmod{998244353}$.
Notes
Under the constraints of this problem, for $E$ in each query, $X \times E=Y$ holds for some integer that is not a multiple of $998244353$, namely $X$, and some integer $Y$.
For these $X,Y$, there exists a unique integer with $X \times Z \equiv Y \pmod{998244353}$ that is at least $0$ and less than $998244353$, namely $Z$. Using this $Z$, we define $E \pmod{998244353}:=Z$.
Note that many pairs satisfying $X \times E =Y$ can be considered, consisting of an integer that is not a multiple of $998244353$, namely $X$, and an integer $Y$; however, $Z$ does not depend on the choice of $X,Y$ and is determined only by $E$.
Constraints
- $1 \leq N \leq 5000$.
- $0 \leq P_i \lt i \quad (0 \leq i \leq N)$.
- $1 \leq W_i \leq 10^5 \quad (0 \leq i \leq N)$.
- $1 \leq Q \leq 20$.
- $0 \leq A_q \leq N \quad (1 \leq q \leq Q)$.
- $0 \leq K_q \leq 10^9 \quad (1 \leq q \leq Q)$.
- All input values are integers.
Input
The input is given from standard input in the following format.$N$ $P_1$ $P_2$ $\dots$ $P_N$ $W_1$ $W_2$ $\dots$ $W_N$ $Q$ $A_1$ $K_1$ $A_2$ $K_2$ $\vdots$ $A_Q$ $K_Q$
Output
The output consists of $Q$ lines. On line $q~(1 \leq q \leq Q)$, print the answer to query $q$ as an integer on $1$ line.
Do not forget the newline at the end.
Sample
Sample 1
Input
3 0 0 2 1 2 3 4 0 3 1 3 2 3 3 3
Output
1 776412275 554580197 665496236
The possible ways Cherry can move are as follows.
- Vertex $0$ $\to$ vertex $1$ $\to$ vertex $0$ $\to$ vertex $1$ : probability $\frac{1}{9}$
- Vertex $0$ $\to$ vertex $1$ $\to$ vertex $0$ $\to$ vertex $2$ : probability $\frac{2}{9}$
- Vertex $0$ $\to$ vertex $2$ $\to$ vertex $3$ $\to$ vertex $0$ : probability $\frac{2}{3}$
Also, for example, $9 \times E_1=4$ and $9 \times 776412275 \equiv 4 \pmod{998244353}$, so $E_1 \pmod{998244353}=776412275$.
Sample 2
Input
1 0 46 4 0 46 1 46 0 0 1 0
Output
23 23 0 0
Cherry goes back and forth between vertex $0$ and vertex $1$.
Sample 3
Input
15 0 1 2 2 3 1 4 6 8 9 1 11 8 10 7 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 20 0 20150821 1 20160406 2 20160810 3 20161130 4 20170405 10 20170719 5 20171025 6 20180307 7 20180815 8 20190227 11 20200821 12 20201007 0 20201014 1 20201209 2 20210414 3 20211013 4 20220406 13 20220803 14 20221108 15 20221109
Output
984593583 66562935 853150486 450394280 487556810 425770516 164383442 737722434 878250685 64190509 176934106 581447838 504103921 609099868 775475173 525420298 255941538 712197622 537846225 240794030
$A_1, \dots, A_M$ are not necessarily in ascending order and may contain duplicates.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。