No.1750 ラムドスウイルスの感染拡大-hard
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 139
作問者 :
ramdos
/ テスター :
箱星
タグ : / 解いたユーザー数 139
作問者 :
ramdos
/ テスター :
箱星
問題文最終更新日: 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 日目 |
|---|---|---|---|
| 都市 0 | 1 | 0 | 2 |
| 都市 1 | 0 | 1 | 1 |
| 都市 2 | 0 | 1 | 1 |
サンプル2
入力
5 7 4 0 1 0 3 0 4 1 3 1 4 2 4 3 4
出力
22
感染者数は以下の表のようになります。
| 都市 | 0 日目 | 1 日目 | 2 日目 | 3 日目 | 4 日目 |
|---|---|---|---|---|---|
| 都市 0 | 1 | 0 | 3 | 6 | 22 |
| 都市 1 | 0 | 1 | 2 | 7 | 21 |
| 都市 2 | 0 | 0 | 1 | 2 | 8 |
| 都市 3 | 0 | 1 | 2 | 7 | 21 |
| 都市 4 | 0 | 1 | 2 | 8 | 22 |
サンプル3
入力
6 2 10 2 4 3 5
出力
0
ウイルスは一瞬で収束します。
サンプル4
入力
3 2 1000000000000000000 0 1 0 2
出力
292427463
998244353 で割ったあまりを求めることに注意してください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。