近い問題を何度か見たしね。
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; }
まとめ
状態の行列を作るのが面倒くさかった。よく一発で通ったな。