http://tdpc.contest.atcoder.jp/tasks/tdpc_house

問題概要

H階建ての家があり、各階には部屋が1番～R番までのR個存在する。部屋間を以下のルールに従って移動するとき、H階の部屋1から1階の部屋1に移動する経路は何通りあるか。ルール1. h階の部屋rから(h-1)階の部屋rへ移動できる。ルール2. 同じ階の部屋間は、与えられる行列Gの対応要素が1であれば相互に移動可能。ルール3. 同じ部屋を2度通ることはできない。

H <= 10⁹

R <= 16

解法

横方向の移動の仕方をbitDPで計算した後、縦方向の移動の仕方を行列累乗で求める。

「その階で最初に部屋xにいて最後に部屋yにいたときの移動経路の総数」をすべてのx, y(1 <= x, y <= R)の組合せで求めると、これをR行R列の行列の形で表すことができる。すべての階で部屋の構造は同じなので、あとはH階分の行列累乗を行えばH階→1遷への遷移を求めることができる。

問題は「その階で最初に部屋xにいて最後に部屋yにいたときの移動経路の総数」をどう求めるかということであるが、これはbitDPで行うことができる。具体的には

dp(i, j, mask): 「その階で最初にいた部屋がiで、部屋集合maskをこれまでに通過し、最後にjにいる」ときの移動経路の総数

となる。遷移の際に経由する部屋を総当たりする必要があるのでこのdpの計算はO(R³×2^R)になる。行列累乗パートも考慮に入れると計算量はO(R³×2^R + R³×logH)となる。R=16だと若干怪しくなってくる計算量だが実はTDPCでこの問題だけTLが8secもあるので余裕を持って間に合う。

感想

最初2^R×R³の桁を一個見間違えて無駄に迷走してしまった……

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop;
 
immutable long MOD = 10^^9+7;
 
void main() {
    auto s = readln.split.map!(to!int);
    auto H = s[0];
    auto R = s[1];
    auto G = R.iota.map!(_ => readln.split.map!(to!int).array).array;
 
    
    auto dp = new long[][][](R, R, 1 << R);
    foreach (i; 0..R) dp[i][i][1<<i] = 1;
    auto masks = (1<<R).iota.array.sort!((a, b) => a.popcnt < b.popcnt).array;
 
    foreach (i; 0..R) // 出発
        foreach (mask; masks)
            foreach (j; 0..R) // 経由
                foreach (k; 0..R) { // 到着
                    if (!(mask & (1 << i))) continue;
                    if (!(mask & (1 << j))) continue;
                    if ((mask & (1 << k))) continue;
                    if (!G[j][k]) continue;
                    (dp[i][k][mask|(1<<k)] += dp[i][j][mask]) %= MOD;
                }
 
    
    auto mat = new long[][](R, R);
    foreach (i; 0..R)
        foreach (j; 0..R)
            foreach (mask; 0..1<<R)
                (mat[i][j] += dp[i][j][mask]) %= MOD;
 
    matpow(R, H, mat)[0][0].writeln;
}
 
 
long[][] matmul(int N, long[][] m1, long[][] m2) {
    auto ret = new long[][](N, N);
    foreach (i; 0..N) {
        foreach (j; 0..N) {
            ret[i][j] = 0;
            foreach (k; 0..N) {
                (ret[i][j] += m1[i][k] * m2[k][j] % MOD) %= MOD;
            }
        }
    }
    return ret;
}
 
long[][] matpow(int N, long K, long[][] mat) {
    auto ret = new long[][](N, N);
    foreach (i; 0..N)
        foreach (j; 0..N)
            ret[i][j] = i == j ? 1 : 0;
    
    while (K > 0) {
        if (K % 2 == 1)
            ret = matmul(N, ret, mat);
        mat = matmul(N, mat, mat);
        K /= 2;
    }
 
    return ret;
}

nebukuro09の日記

Typical DP Contest M - 家

問題概要

解法

感想

コード (D言語)