题目描述
N 個の頂点と M 本の辺からなる連結かつ単純な無向グラフが与えられます。
i = 1, 2, …, M について、i 番目の辺は頂点 ui と頂点 vi を結んでいます。
高橋君は、はじめレベルが 0 の状態で頂点 1 におり、下記の行動をちょうど K 回行います。
- まず、いまいる頂点に隣接する頂点の中から、1 つを等確率でランダムに選択し、その頂点に移動する。
- その後、移動後の頂点 v に応じて、下記のイベントが発生します。
- Cv = 0 のとき : 高橋君のレベルが 1 だけ増加する。
- Cv = 1 のとき : 高橋君のいまのレベルを X とする。高橋君は X2 円のお金を獲得する。
上記の K 回の行動の過程で高橋君が獲得するお金の合計金額の期待値を mod 998244353 で出力してください(注記参照)。
输入格式
入力は以下の形式で標準入力から与えられる。
N M K u1 v1 u2 v2 ⋮ uM vM C1 C2 … CN
输出格式
答えを出力せよ。
题目大意
给出一个 n 个点 m 条边的无向简单连通图,每个点有一个点权 Ci∈{0,1}。
Takahashi 初始时在 1 号点,等级为 0。接下来他要做 K 次如下操作:
- 随机地走向当前所在点的一个相邻点。
- 如果这个点 Ci=0,将等级加一;如果这个点 Ci=1,设 Takahashi 当前的等级为 X,他可以获得 X2 元钱。
求 K 次操作中 Takahashi 一共获得的钱数的期望,答案对 998244353 取模。
(1≤n,m,K≤3000)
提示
注記
求める期待値は必ず有理数となることが証明できます。またこの問題の制約下では、その値を互いに素な 2 つの整数 P, Q を用いて QP と表したとき、R × Q ≡ P(mod998244353) かつ 0 ≤ R < 998244353 を満たす整数 R がただ一つ存在することが証明できます。この R を求めてください。
制約
- 2 ≤ N ≤ 3000
- N−1 ≤ M ≤ min{ N(N−1)/2, 3000}
- 1 ≤ K ≤ 3000
- 1 ≤ ui, vi ≤ N
- ui = vi
- i = j ⟹ { ui, vi} = { uj, vj }
- 与えられるグラフは連結
- Ci ∈ { 0, 1}
- 入力はすべて整数
Sample Explanation 1
高橋君の移動経路として考えられるものは複数ありますが、ここでは例として、高橋君が頂点 1 を始点として、1 → 2 → 4 → 5 → 4 → 2 → 1 → 2 → 3 と移動する場合に獲得するお金の合計金額を計算します。 1. 高橋君は 1 回目の行動で、いまいる頂点 1 に隣接する頂点 2 に移動します。C2 = 0 であるため、その後高橋君のレベルが 1 に上がります。 2. 高橋君は 2 回目の行動で、いまいる頂点 2 に隣接する頂点 4 に移動します。C4 = 1 であるため、その後高橋君は 12 = 1 円を獲得します。 3. 高橋君は 3 回目の行動で、いまいる頂点 4 に隣接する頂点 5 に移動します。C5 = 0 であるため、その後高橋君のレベルが 2 に上がります。 4. 高橋君は 4 回目の行動で、いまいる頂点 5 に隣接する頂点 4 に移動します。C4 = 1 であるため、その後高橋君は 22 = 4 円を獲得します。 5. 高橋君は 5 回目の行動で、いまいる頂点 4 に隣接する頂点 2 に移動します。C2 = 0 であるため、その後高橋君のレベルが 3 に上がります。 6. 高橋君は 6 回目の行動で、いまいる頂点 2 に隣接する頂点 1 に移動します。C1 = 0 であるため、その後高橋君のレベルが 4 に上がります。 7. 高橋君は 7 回目の行動で、いまいる頂点 1 に隣接する頂点 2 に移動します。C2 = 0 であるため、その後高橋君のレベルが 5 に上がります。 8. 高橋君は 8 回目の行動で、いまいる頂点 2 に隣接する頂点 3 に移動します。C3 = 1 であるため、その後高橋君は 52 = 25 円を獲得します。 よって、高橋君が獲得するお金の合計金額は、1 + 4 + 25 = 30 円です。