DPまとめコンテスト/R - Walk - 競技プログラミング用 知識集積所【7/19更新】

---

問題

DP-R

必要知識

ABCのB以下レベルの内容は省略

• 隣接行列（未作成）
• 行列計算（未作成）
• ダブリング（未作成）
• 剰余類環

……DPまとめコンテストとは？

考え方

隣接行列（未作成）をk乗すれば、各点から各点へkステップで移動する経路数がわかる。
つまり、その成分を全部足せばOK。

kが非常に大きいので、k乗にはダブリング（未作成）を使うこと。

答えはmod10^9+7での値なので、剰余類環も参照。

……DPまとめコンテストとは？

解答例

解答例

注意点

別解