AT_oupc2023_day1_g Impassable Game

$ N $ 頂点 $ M $ 辺の有向グラフ $ G $ および 正の整数 $ K $ が与えられます。 $ G $ の頂点および辺には頂点 $ 1 $ , 頂点 $ 2 $ , ..., 頂点 $ N $ および 辺 $ 1 $ , 辺 $ 2 $ , ..., 辺 $ M $ と番号づけられており、辺 $ i $ ( $ 1 \leq i \leq M $ ) は 頂点 $ u_i $ から 頂点 $ v_i $ へ向かう辺で、パラメータ $ b_i $ が付加されています。 $ b_i $ は $ 0 $ または $ 1 $ です。 有向グラフ $ G $ について、以下の $ 3 $ つのことが保証されます。 - $ G $ は多重辺を持たない。 - $ G $ はサイクルを持たない。 - 各頂点は頂点 $ 1 $ から辺をたどることで到達でき、頂点 $ 1 $ からの最短経路の長さと最長経路の長さは一致し、それは $ K $ 以下である。 $ 2 $ つの駒を使って、 $ 2 $ 人のプレイヤーがゲームを行います。 - 最初、各プレイヤーは自分の駒を頂点 $ 1 $ に置く。 - プレイヤーは自分のターンになったら以下の操作のどちらかを行う。 - 移動 : 自分の駒をちょうど $ 1 $ 回移動させる。自分の駒が頂点 $ i $ にあるとき、頂点 $ i $ から頂点 $ j $ へ向かう辺があるような頂点 $ j $ へのみ移動させることができる。ただし、自分の駒が頂点 $ 1 $ にあるときは、移動できる頂点から等確率でランダムに $ 1 $ つ選んで移動させなければならない。また、先手のプレイヤーは全ての辺を、後手のプレイヤーは $ b_i=0 $ である辺のみを使用することができる。 - 敗北宣言 : 自分の負け、相手の勝ちとしてゲームを終了とする。 - 先手のプレイヤーから交互にターンを繰り返し、敗北宣言が行われないならば、後手のプレイヤーが 移動を $ K $ 回行った直後の時点でゲームを終了とする。その時点で $ 2 $ つの駒が同じ頂点にあるなら後手の勝ち、異なる頂点にあるなら先手の勝ちとなる。 各プレイヤーは自分の勝ちを目指して最適な戦略を取ります。 先手のプレイヤーが勝つ確率を $ \bmod $ $ 998244353 $ で求めてください。 確率 $ \bmod $ $ 998244353 $ の定義 この問題で求める確率は必ず有理数になることが証明できます。また、この問題の制約下では、求める確率を既約分数 $ \frac{y}{x} $ で表したときに $ x $ が $ 998244353 $ で割り切れないことが保証されます。このとき、 $ y≡xz \pmod {998244353} $ を満たす $ 0 \leq z < 998244353 $ がただ一つ存在するので、 $ z $ を出力してください。

入力は以下の形式で標準入力から与えられます。 > $ N $ $ M $ $ K $ $ u_1 $ $ v_1 $ $ b_1 $ $ u_2 $ $ v_2 $ $ b_2 $ $ \vdots $ $ u_M $ $ v_M $ $ b_M $

先手のプレイヤーが勝つ確率を $ \bmod $ $ 998244353 $ で出力してください。

### 小課題 1. ( $ 1 $ 点) $ N\leq100 $ , $ M\leq1000 $ 2. ( $ 99 $ 点) 追加の制約はない ### Sample Explanation 1 各プレイヤーが駒を $ 1 $ 回移動させた時点で、先手の駒が存在する頂点を $ i $ 、後手の駒が存在する頂点を $ j $ としたときの組 $ (i, j) $ のうち、先手が勝つ組と後手が勝つ組はそれぞれ以下です。 - 先手が勝つ組 : $ (2, 3) $ 、 $ (3, 3) $ - 後手が勝つ組 : $ (2, 2) $ 、 $ (3, 2) $ この $ 4 $ つの組のうち、 $ (3, 2) $ が選ばれたとき、以下のような進行が考えられます。 - まず頂点 $ 1 $ に駒を置く。 - 先手が辺 $ 2 $ を使用して自分の駒を頂点 $ 3 $ へ移動させる。 - 後手が辺 $ 1 $ を使用して自分の駒を頂点 $ 2 $ へ移動させる。 - 先手が辺 $ 6 $ を使用して自分の駒を頂点 $ 5 $ へ移動させる。 - 後手が辺 $ 4 $ を使用して自分の駒を頂点 $ 5 $ へ移動させる。 - 後手が駒を $ 2 $ 回動かしたのでゲームを終了とする。 $ 2 $ つの駒が頂点 $ 5 $ に存在するため後手の勝ち 他にもゲームの進行は考えられますが、 $ (3, 2) $ が選ばれた場合、先手がどのような戦略を取っても後手が勝つことができます。 なお、先手が勝つ確率は $ \frac{1}{2} $ と求めることができ、これを $ \bmod $ $ 998244353 $ で表現すると $ 499122177 $ となります。 このテストケースは小課題 1 の制約を満たします。 ### Sample Explanation 2 各プレイヤーが駒を $ 1 $ 回移動させた時点で、先手の駒が存在する頂点を $ i $ 、後手の駒が存在する頂点を $ j $ としたときの組 $ (i, j) $ のうち、先手が勝つ組と後手が勝つ組はそれぞれ以下です。 - 先手が勝つ組 : $ (2, 3) $ 、 $ (3, 2) $ 、 $ (3, 3) $ - 後手が勝つ組 : $ (2, 2) $ この $ 4 $ つの組のうち、 $ (3, 2) $ が選ばれたとき、以下のような進行が考えられます。 - まず頂点 $ 1 $ に駒を置く。 - 先手が辺 $ 2 $ を使用して自分の駒を頂点 $ 3 $ へ移動させる。 - 後手が辺 $ 1 $ を使用して自分の駒を頂点 $ 2 $ へ移動させる。 - 先手が辺 $ 5 $ を使用して自分の駒を頂点 $ 5 $ へ移動させる。 - 後手が辺 $ 3 $ を使用して自分の駒を頂点 $ 4 $ へ移動させる。 - 後手が駒を $ 2 $ 回動かしたのでゲームを終了とする。 $ 2 $ つの駒が異なる頂点に存在するため先手の勝ち 他にもゲームの進行は考えられますが、 $ (3, 2) $ が選ばれた場合、後手がどのような戦略を取っても先手が勝つことができます。 なお、先手が勝つ確率は $ \frac{3}{4} $ と求めることができ、これを $ \bmod $ $ 998244353 $ で表現すると $ 249561089 $ となります。 このテストケースは小課題 1 の制約を満たします。 ### Sample Explanation 3 後手は 移動を $ 1 $ 回も行うことなく敗北宣言しなければなりません。 このテストケースは小課題 1 の制約を満たします。 ### Sample Explanation 4 このテストケースは小課題 1 の制約を満たします。 ### Constraints - $ 2 \leq N \leq 4{,}000 $ - $ 1 \leq M \leq 2 \times 10^{6} $ - $ 1 \leq K \leq 4{,}000 $ - $ 1 \leq u_i, v_i \leq N $ - $ b_i \in \{0, 1\} $ - $ G $ は多重辺を持たない。 - $ G $ はサイクルを持たない。 - 各頂点は頂点 $ 1 $ から辺をたどることで到達でき、頂点 $ 1 $ からの最短経路の長さと最長経路の長さは一致し、それは $ K $ 以下である。 - 入力はすべて整数