Typical DP Contest : M - 家

これもなんとか自力で解けた。
http://tdpc.contest.atcoder.jp/tasks/tdpc_house

問題

H階建ての家があり、各階にはR個の部屋がある。
各階、部屋同士の行き来が可能かどうかが隣接行列で与えられる。
また、各階から下の階に移動できる。

H階の１番目の部屋から1階の１番目の部屋に移動する、同じ部屋を２度通らない移動手順を数え上げよ。

解法

まず、高さ方向は後にしてして部屋i→部屋jに移動する組み合わせ数を、行列A[i][j]で表す。
これはBitDPを使って部屋iからスタートしてまだ通っていない部屋を通る通り方を足しこんでいけばよい。
計算量はかな。

H階の１番目の部屋から1階の１番目の部屋に移動する手順を考えると、各階で部屋x→部屋yに移動する、と考える。
初期状態をベクトル(1,0,0,0,....0)にA^Hをかけ、先頭要素を取得すればよい。

int H,R;
ll npat[2][20];
ll mo=1000000007;
ll p[17][100000];

const int MAT=20;
int G[MAT][MAT];
ll pat[MAT][MAT];
void powmat(int p,int n,ll a[MAT][MAT],ll r[MAT][MAT]) {
	int i,x,y,z;
	ll a2[MAT][MAT];
	FOR(x,n) FOR(y,n) a2[x][y]=a[x][y];
	FOR(x,n) FOR(y,n) r[x][y]=0;
	FOR(i,n) r[i][i]=1;
	while(p) {
		ll h[MAT][MAT];
		if(p%2) {
			FOR(x,n) FOR(y,n) {
				h[x][y]=0;
				FOR(z,n) h[x][y] += (r[x][z]*a2[z][y]) % mo;
				h[x][y] %= mo;
			}
			FOR(x,n) FOR(y,n) r[x][y]=h[x][y];
		}
		FOR(x,n) FOR(y,n) {
			h[x][y]=0;
			FOR(z,n) h[x][y] += (a2[x][z]*a2[z][y]) % mo;
			h[x][y] %= mo;
		}
		FOR(x,n) FOR(y,n) a2[x][y]=h[x][y];
		p>>=1;
	}
}

void getpat(int s) {
	int f,x,mask;
	
	ZERO(p);
	p[s][1<<s]=1;
	
	ll tot=0;
	FOR(mask,1<<R) {
		FOR(f,R) {
			if((mask & (1<<f))==0) continue;
			FOR(x,R) if(G[f][x] && ((mask & (1<<x))==0)) {
				p[x][mask | (1<<x)] += p[f][mask];
				p[x][mask | (1<<x)] %= mo;
			}
			pat[s][f] += p[f][mask];
		}
	}
	FOR(f,R) pat[s][f] %= mo;
	return;
}

void solve() {
	int f,r,i,j,k,l, x,y,z,mask=0;
	
	cin>>H>>R;
	FOR(x,R) FOR(y,R) G[x][y]=GETi();
	FOR(x,R) getpat(x);
	
	ZERO(npat[0]);
	npat[0][0]=1;
	
	ll pp[MAT][MAT];
	powmat(H,R,pat,pp);
	FOR(x,R) FOR(y,R) npat[1][y]+=(npat[0][x]*pp[x][y]) % mo;
	return _P("%lld\n",npat[1][0]%mo);
}

まとめ

行列の累乗計算はライブラリがないので自作した。