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 ですよね.通るもんですね)