問題一覧 > 通常問題

No.2832 Nana's Fickle Adventure

レベル : / AI推定難易度 : 1825 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 22
作問者 : twitteryou / テスター : 👑 p-adic
お気に入りにしたユーザー ProblemId : 10945 / 自分の提出
問題文最終更新日: 2024-08-04 08:22:26
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 439 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。