yukicoder : No.541 3 x N グリッド上のサイクルの個数

近い問題を何度か見たしね。
https://yukicoder.me/problems/no/541

問題

縦に4行、横に(N+1)列分、計4*(N+1)個の頂点が格子状に並んでおり、格子上で隣接する頂点同士に辺が張られているグラフを考える。
このグラフの部分グラフのうち、単純閉路を成すものは何通りあるか。

解法

閉路を成すということは、隣接する列同士の頂点をつなぐ4本の辺のうち、部分グラフでは0,2,4本のいずれかを選択した状態になるはずである。
端の列から順に、直前の列の状態からの遷移を行列で表現し、行列累乗で組み合わせを求めよう。

たとえば左端の列から順に列を決めていくとき、列の状態は以下の10通りある。

• 横辺が0本選択されている
  • まだ閉路が始まっていない場合と、すでに左側で閉路が出来上がってしまっており、これ以上辺を追加できない場合の2通り
• 横辺が2本選択されている
  • 4本中2本選択されている場合が6通り。
• 横辺が4本すべて選択されている
  • 手前の列で最上段と最下段の辺がつながっているケースと、上2段・下2段がつながっているケースの2通りがある。

ll mo=1000000007;
const int MAT=10;
struct Mat { ll v[MAT][MAT]; };
Mat mulmat(Mat& a,Mat& b,int n=MAT) {
	ll mo2=4*mo*mo;
	int x,y,z; Mat r;
	FOR(x,n) FOR(y,n) r.v[x][y]=0;
	FOR(x,n) FOR(z,n) FOR(y,n) {
		r.v[x][y] += a.v[x][z]*b.v[z][y];
		if(r.v[x][y]>mo2) r.v[x][y] -= mo2;
	}
	FOR(x,n) FOR(y,n) r.v[x][y]%=mo;
	return r;
}

Mat powmat(ll p,Mat a,int n=MAT) {
	int i,x,y; Mat r;
	FOR(x,n) FOR(y,n) r.v[x][y]=0;
	FOR(i,n) r.v[i][i]=1;
	while(p) {
		if(p%2) r=mulmat(r,a,n);
		a=mulmat(a,a,n);
		p>>=1;
	}
	return r;
}

ll N;

string m[10]={
	"1000000000",
	"1111000010",
	"1111110000",
	"1111111100",
	"1011110000",
	"1011111000",
	"1001011010",
	"1100001100",
	"0001000010",
	"0111111011",
};

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	Mat G,G2;
	FOR(x,10) FOR(y,10) G.v[x][y]=m[x][y]-'0';
	cin>>N;
	G2=powmat(N+1,G);
	cout<<G2.v[9][0]<<endl;
}

まとめ

状態の行列を作るのが面倒くさかった。よく一発で通ったな。