kazuma8128’s blog

競プロの面白い問題を解きます

CodeChef January Lunchtime 2019 Wanderer

問題概要

N 頂点 M 辺の無向単純グラフ上を K 回移動する. 始点は頂点1. Q個の条件が次のように与えられる.
(a_i, b_i) : b_i 回目の移動後に頂点 a_i にいる.
このとき, 全ての条件を満たすような動きの場合の数 mod 1e9+7 を求めよ.

  • 1 <= N, M, K, Q <= 9000

解法

dp[i][j] : i 回の移動後に頂点 j にいる場合の数
を基本的に求めていく.
各 b_i 回目の移動後に 頂点 a_i 以外の値を 0 で埋めると条件を満たすもののみ求まる.
このとき, 遷移を隣接行列の掛け算でやると O(KN^2) になってしまうが, 冷静に考えると遷移は O(M) で十分なので毎回各辺を回すだけで O(KN+KM) になる.

ソースコード

https://www.codechef.com/viewsolution/22638027

コンテスト中に焦って書いたコードなので読みにくいかも.