Typical DP Contest M - 家
解法
まず階段を使うまえに,各階で部屋i -> j の移動経路が何パターンあるかを計算します.
これは普通に
dp[S][i][j] := 今まで訪れた部屋の集合が S である,i -> j の移動パターン
とすれば求めることができます.
i -> jの移動パターンの総数を A[j][i] で表すことにします.(添字注意)
h 階で部屋 i に至る経路の総数を b_h[i] という列ベクトルで表すと,h - 1 階で部屋 i に至る経路の総数 b_{h-1}[i] は b_{h-1} = A * b_h という式で表せることがわかります.
H回部屋をウロウロできるので,答えは A^H * b_H となります.b_H は最初の要素が1でほかが0の列ベクトルです.
計算量は O(2^H * R^3 + R^3logH) です.
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; constexpr ll M = 1e9 + 7; // matrix は略 ll dp[1 << 16][16][16]; int main() { int H, R; cin >> H >> R; vector<vector<int>> g(R, vector<int>(R)); for(int i = 0; i < R; ++i) { for(int j = 0; j < R; ++j) { cin >> g[i][j]; } } for(int i = 0; i < R; ++i) { dp[1 << i][i][i] = 1; } auto A = make_matrix<ll>(R, R); for(int S = 0; S < (1 << R); ++S) { for(int start = 0; start < R; ++start) { for(int now = 0; now < R; ++now) { for(int next = 0; next < R; ++next) { if((S >> next) & 1 || g[now][next] == 0) { continue; } (dp[S | 1 << next][start][next] += dp[S][start][now]) %= M; } (A[now][start] += dp[S][start][now]) %= M; } } } A = modpow(A, H, M); vector<ll> b(R); b[0] = 1; cout << modmul(A, b, M)[0] << endl; }
感想
これは簡単だった.
2^R * R^3 でちょっと焦りましたが…(よくあるのは 2^R * R^2 ですよね.通るもんですね)