No.2832 Nana's Fickle Adventure
タグ : / 解いたユーザー数 22
作問者 :
Problem Statement
Nana has come to a magical country. The country consists of $N$ towns and $M$ roads. Road $i\ (1 \leq i \leq M)\ $ connects towns $U_i$ and $V_i$ bidirectionally.
Nana is going to adventure in this magical country for $X$ days. On day $i$ $\ (1 \leq i \leq X)\ $, she acts as follows.
・Among the roads connected to the town she is currently in, she randomly chooses $1$ road and moves using that road. However, from day $2$ onward, she does not choose the road she chose on the previous day. Also, if there is no road she can move along, she does not move on that day.
Each of the candidate roads is equally likely to be chosen, that is, the choice is uniformly random. Before the move on day $1$, she is in town $1$.
For $t=1,2,\ldots,N\ $, find the probability that Nana is in town $t$ when her action on day $X$ has finished, modulo $\mod 998244353\ $. That is, in each case the probability is a rational number whose irreducible fraction representation has a denominator coprime to $998244353$, so when the answer as an irreducible fraction is $\frac{p}{q}$, find the integer $x\ (0 \leq x \leq 998244352)\ $ such that $\ qx=p\pmod{998244353}\ $.
In this country, there may be roads that lead back to the same town, there may be many roads connecting a certain pair of $2$ towns, and there may even be towns that cannot be reached from town $1$ no matter which roads are taken. That is, the graph may be disconnected and may contain multiple edges and self-loops.
Input
$N\ M \ X$ $U_1 \ V_1$ $U_2 \ V_2$ $\vdots$ $U_M \ V_M$
・$2 \leq N \leq 10$
・$1 \leq M \leq 1000$
・$1 \leq X \leq 10^8$
・$1 \leq U_i,V_i \leq N\ (1 \leq i \leq M)$
・$N,M,X,U_i,V_i\ (1 \leq i \leq M)\ $ are all integers
Output
Output $N$ lines. On line $i$, output the probability that she is in town $i$.
Sample
Sample 1
Input
3 5 2 1 2 1 2 2 2 1 3 3 3
Output
332748118 332748118 332748118
First, on day $1$, Nana chooses each of roads $1,2,4$ with probability $\frac{1}{3}$. If she chooses road $1$, then on day $2$ she is in town $2$ and moves by choosing each of roads $2,3$ with probability $\frac{1}{2}$.
Moving in this way, after her action on day $2$ has finished, the probabilities that she is in towns $1,2,3$ are each $\frac{1}{3}$.
Sample 2
Input
5 5 11 1 2 2 3 3 4 4 5 5 5
Output
0 1 0 0 0
On day $10$, she is always in town $1$ having passed through road $1$ on the previous day, but since she cannot choose the road she passed through on the previous day, she cannot act. However, on day $11$, she is able to choose road $1$.
Sample 3
Input
3 2 100000000 1 1 2 2
Output
1 0 0
In some cases, she cannot leave town $1$ in the first place.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。