問題一覧 > 通常問題

No.1750 ラムドスウイルスの感染拡大-hard

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 107
作問者 : ramdosramdos / テスター : 👑 koboshikoboshi
3 ProblemId : 7189 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-10-21 21:35:27

問題文

$0,1,\ldots,N-1$ の番号のついた $N$ 個の都市と $M$ 本の道路があります。 道路 $i$ を使うことで、都市 $s_i$ と都市 $t_i$ を双方向に行き来できます。

各都市には無限に人間が居ます。

$0$ 日目に、都市 $0$ で初めてラムドスウイルスの感染者が $1$ 人出ました。

特定の都市における $i$ 日目のラムドスウイルスの感染者は常に、その都市と直接道路で行き来できるすべての都市の $i-1$ 日目の感染者の合計です。

$T$ 日目の都市 $0$ におけるラムドスウイルスの感染者数を 998244353 で割ったあまりを求めてください。

入力

$N$ $M$ $T$
$s_0$ $t_0$
$s_1$ $t_1$
$\vdots$
$s_{M-1}$ $t_{M-1}$
  • $2 \leq N \leq $ $100$
  • $1 \leq M \leq \min\left(\dfrac{N(N-1)}{2} ,1 000\right)$
  • $1 \leq T \leq$ $10^{18}$
  • $0 \leq s_{i} \lt t_{i} \leq N-1$
  • 組 $(s_i,t_i)$ は全て相異なる
  • 入力は全て整数である

出力

整数で出力してください。

サンプル

サンプル1
入力
3 3 2
0 1
0 2
1 2
出力
2

感染者数は以下の表のようになります。

都市0 日目1 日目2 日目
都市 0102
都市 1011
都市 2011
サンプル2
入力
5 7 4
0 1
0 3
0 4
1 3
1 4
2 4
3 4
出力
22

感染者数は以下の表のようになります。

都市0 日目1 日目2 日目3 日目4 日目
都市 0103622
都市 1012721
都市 20012 8
都市 3012721
都市 4012822
サンプル3
入力
6 2 10
2 4
3 5
出力
0

ウイルスは一瞬で収束します。

サンプル4
入力
3 2 1000000000000000000
0 1
0 2
出力
292427463

998244353 で割ったあまりを求めることに注意してください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。