Typical DP Contest M - 家

問題

tdpc.contest.atcoder.jp

解法

mat[i][j] = (同じ部屋に訪れることなく部屋 i から部屋 j に行く方法) とします。

これが求まったとすると, dp[h][i] = (h 階において 部屋 i にいる場合の数) というのは,
dp[h+1][i] = dp[h][k] * mat[k][i] となります(階段は上に登っていくとしています)。

この掛け算, 行列とベクトルの掛け算っぽいです。なので, 行列の累乗を log H で求めれば素早く答えを求められることになります(これはよくあるテク)。

ということで, あと求めるべきは mat[i][j] です。これは bitDP でなんとかなります。

dp[now][state] = (到達済みの頂点の集合が state, 今いる頂点が now であるような場合の数)とします。この dp の遷移は,
dp[next][state|(1< state の順番に回すと正しい答えが出ません。(dp は state の小さい順には DAG っぽく考えられるけど, now の順番ではそうでないため)

typedef long long number;
typedef vector<number> vec;
typedef vector<vec> matrix;

const ll MOD = 1e9+7;

// O( n )
matrix ident(int n) {
    matrix A(n, vec(n));
    for (int i = 0; i < n; ++i) A[i][i] = 1;
    return A;
}
// O( n^3 )
matrix mul(const matrix &A, const matrix &B) {
    matrix C(A.size(), vec(B[0].size()));
    for (int i = 0; i < (int)C.size(); ++i)
        for (int j = 0; j < (int)C[i].size(); ++j)
            for (int k = 0; k < (int)A[i].size(); ++k) {
                C[i][j] += A[i][k] * B[k][j];
                C[i][j] %= MOD;
            }
    return C;
}
// O( n^3 log e )
matrix pow(const matrix &A, ll e) {
    if (e == 0) return ident(A.size());
    if (e == 1) return A;
    if (e % 2 == 0) {
        matrix tmp = pow(A, e/2);
        return mul(tmp, tmp);
    } else {
        matrix tmp = pow(A, e-1);
        return mul(A, tmp);
    }
}

const int MAXR = 16;
int H, R;
int G[MAXR][MAXR];

ll dp[MAXR][1<<MAXR];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> H >> R;
    for (int i = 0; i < R; i++) for (int j = 0; j < R; j++) {
    	cin >> G[i][j];
    }
    matrix mat(R, vec(R));
    for (int s = 0; s < R; s++) {
    	memset(dp, 0, sizeof(dp));
    	dp[s][1<<s] = 1;
        for (int state = 0; state < 1<<R; state++) {
    	   for (int now = 0; now < R; now++) {
    			if (!dp[now][state]) continue;
    			for (int next = 0; next < R; next++) {
    				if ((state>>next)&1) continue;
    				if (!G[now][next]) continue;
    				(dp[next][state|(1<<next)] += dp[now][state]) %= MOD;
    			}
    		}
    	}
    	for (int i = 0; i < R; i++) {
    		for (int j = 0; j < 1<<R; j++) {
    			(mat[s][i] += dp[i][j]) %= MOD;
    		}
    	}
    }
    mat = pow(mat, H);
    cout << mat[0][0] << endl;
    return 0;
}