Typical DP Contest M - 家

問題

H階建ての家がある。各階は全て同じ構造をしていて、r部屋からなり、
g[i][j] = 1のとき部屋iから部屋jへ行くことができる。
また、h階の部屋iからはh-1階の部屋iへ降りることができる。（登れない）

H階の部屋1から1階の部屋1まで、同じ部屋を２度通らないで行く場合の数をmod 10^9 + 7で求めよ。

制約条件

H≦10^9
r≦16

方針

一つの階で同じ部屋を通らずiからjまで行く場合の数は、
巡回セールスマン的なDPで、
dp[bit][i] := bitの部屋を通ってiにいるときの場合の数
をそれぞれの始点kからDPすれば求まる。

すると、1階をi, jまで降りるときの場合の数の行列Aができる。
2階のときはA^2……で、A^Hを繰り返し二乗法で求めればよい。

ソースコード

void calc(int s, vi &way){
	memset(dp, 0, sizeof(dp));
	dp[1 << s][s] = 1;
	
	rep(i, 1 << r) rep(j, r) if(dp[i][j]){
		rep(k, r) if(!(i & 1 << k) && g[j][k]) (dp[i | 1 << k][k] += dp[i][j]) %= mod;
	}
	rep(i, 1 << r) rep(j, r) (way[j] += dp[i][j]) %= mod;
}
 
int main(){
	cin >> h >> r;
	rep(i, r) rep(j, r) cin >> g[i][j];
	
	way.resize(r);
	rep(i, r) way[i].resize(r), calc(i, way[i]);
	
	way = pw(way, h);
	cout << way[0][0] << endl;
	
	return 0;
}