No.2832 Nana's Fickle Adventure
タグ : / 解いたユーザー数 20
作問者 :
ねしん
/ テスター :
👑 
p-adic
問題文
ナナは魔法の国に来ています。その国は$N$個の町と$M$本の道から構成されています。道$i\ (1 \leq i \leq M)\ $は町$U_i$と$V_i$を双方向に結んでいます。
ナナは$X$日間この魔法の国で冒険することになりました。$i$日目$\ (1 \leq i \leq X)\ $では、以下の様に行動します。
・今いる町につながっている道のうち、$1$つの道をランダムに選び、その道を使って移動する。ただし、$2$日目以降は前日に選んだ道は選ばないものとする。また、移動できる道がない場合は、その日は移動しないものとする。
候補にある道のうちどれが選ばれるかは同様に確からしいもの、つまり、等確率とします。$1$日目の移動を行う前は町$1$にいます。
$t=1,2,\ldots,N\ $において$X$日目の行動が終わった時にナナが町$t$にいる確率を$\mod 998244353\ $で求めてください。つまりそれぞれにおいて、確率は分母が$998244353$と互いに素な既約分数表示を持つ有理数になるので、答えが既約分数で$\frac{p}{q}$となるとき$\ qx=p\pmod{998244353}\ $となる整数$x\ (0 \leq x \leq 998244352)\ $を求めてください。
この国では同じ町に戻ってきてしまう道や、ある$2$つの町において、その町同士を結ぶ道がたくさんあったり、そもそも、町$1$からいくつかの道を通っても、ある町にたどり着けない場合もあります。つまり、非連結であったり多重辺や自己ループ辺を含む場合があります。
入力
$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)\ $はすべて整数
出力
$N$行出力してください。$i$行目には町$i$にいる確率を出力してください。
サンプル
サンプル1
入力
3 5 2 1 2 1 2 2 2 1 3 3 3
出力
332748118 332748118 332748118
まず、ナナは$1$日目で道$1,2,4$をそれぞれ$\frac{1}{3}$の確率で選びます。道$1$を選んだ場合、$2$日目では、町$2$にいて、道$2,3$をそれぞれ$\frac{1}{2}$の確率で選んで移動します。
このように移動すると、$2$日目の行動が終わった後、町$1,2,3$にいる確率はそれぞれ、$\frac{1}{3}$になります。
サンプル2
入力
5 5 11 1 2 2 3 3 4 4 5 5 5
出力
0 1 0 0 0
$10$日目では必ず前日に道$1$を通って町$1$にいますが、前日に通った道は選ぶことが出来ないので、行動できません。しかし、$11$日目には道$1$を選ぶことが可能になります。
サンプル3
入力
3 2 100000000 1 1 2 2
出力
1 0 0
そもそも、町$1$から出られないこともあります。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。