考察
ある都市へ来られる旅の数は、前日の全都市の総和から、来られない都市の分だけ引けば求められる。使える道路が多くても、使えない道路が少ないなら、例外を引く方が速い。同じ都市に留まる移動も禁止なので、その分も忘れずに除く。
まず日数と現在地を状態にする。 を「都市1から出発し、 回移動して都市 にいる旅の数」と定義する。都市番号は問題文と同じ1始まりとし、 とする。まだ移動していないときは 、他は0であり、求める答えは である。以後の計算はすべて法998244353で行う。
素直な遷移では、各到着都市について、道でつながった全出発都市の値を足す。しかし使える道路は最大で 本あり、毎日走査すると 時間かかる。入力が列挙しているのは高々5000本の「使えない道路」である。許可された移動を足す代わりに、全体から禁止された移動を引こう。
を都市 と壊れた道路で結ばれた都市の集合とする。前日の全体和を とおくと、遷移は次のように書ける。
第2項は同じ都市に留まる旅、第3項は壊れた道路を使う旅を除く。例えば4都市で、都市2と3の間だけ道が壊れているなら、都市2へ来られるのは都市1と4からだけである。式も となる。
実装では、前日用の配列を読むだけにして、翌日用の配列を別に作る。
- 前日用の配列の総和 を一度求める。
- 全都市 の翌日値を で初期化する。
- 壊れた道路 ごとに、翌日の都市 から前日の を、翌日の都市 から前日の を引く。
- 翌日値を法の非負範囲へ戻し、前日用と翌日用の配列を交換する。
これを の順に行う。毎日、都市と壊れた道路を一度ずつ走査するだけでよい。
典型の発動条件
補集合を使う遷移高速化
許される遷移が多く、禁止される遷移だけが少数列挙されているとき、まず全体の寄与をまとめて足し、例外だけを引く。入力が疎でも、入力された辺が使える辺とは限らない。
ローリング DP
次の日の値が直前の日だけに依存するなら、二つの配列を交換して履歴を省ける。同じ配列を読み書きすると、今日と明日の値が混ざるので注意する。
問題固有の要素
入力された壊れた道路に加えて、自己遷移も禁止されている。問題文の「相異なる都市」を式の に対応付ける。この項は壊れた道路の一覧には現れないので、入力だけを見て遷移を決めない。
正当性
初期値は、移動前に都市1にいる一通りの旅を表す。 が 回移動した旅を正しく数えると仮定し、翌日の到着都市 を固定する。
全体和 は、前日の各旅を出発都市によらず一度ずつ含む。このうち最後の一歩が許されないのは、出発都市が 自身か、集合 に属する場合だけである。壊れた道路は異なる二都市を結び、入力に重複もないため、これらを引くと、許可された移動を一度ずつ数えた和になる。
従って遷移後の配列も正しい旅の数を表す。これを 回繰り返した が、都市1へ戻る旅の数となる。
実装上の注意
- 壊れた道路は双方向なので、両端の翌日値から相手側の前日値を引く。減算の途中でも前日用の配列は変更しない。
- 減算後は法998244353の非負範囲へ戻す。総和や減算をまとめて計算するなら、途中の値に符号付き64 bit整数を使う。
- 壊れた道路が0本なら自己遷移だけを除く。全道路が壊れた小入力では、一度移動した後の値はすべて0になる。
復習の核
- 遷移が多すぎるときは、全体をまとめた後、少ない例外を引けないか考える。
- 禁止条件は入力された道路だけでなく、問題文の自己遷移禁止まで拾う。
- 遷移先の値を計算し終えるまで、遷移元の配列を保つ。
計算量と制約
時間
一日につき総和と翌日値の初期化が 、壊れた道路の両端の減算が 。入力の読み込みを含め、全体で 時間。使える道路を列挙する処理は不要である。
空間
前日・翌日用の二配列に 、壊れた道路の端点の保存に を使い、合計 。日数分の配列は保持しない。
制約との対応
、、壊れた道路は重複のない異なる二都市の組で、 本である。 に抑えられる一方、全都市対を毎日調べると は最大 となる。
出典