AtCoder AGC #003 : F - Fraction of Fractal

こちらはEditorialを見て回答。
http://agc003.contest.atcoder.jp/tasks/agc003_f

問題

H*Wの白黒マスからなる入力グリッドがある。
黒マスは隣接マスに関して連結している。

あるレベルiのグリッドをレベル(i+1)のグリッドにするとは、レベルiのグリッドにおいて黒いマスを入力グリッドに、、白いマスを入力グリッドと等しいサイズのグリッドに置き換える事である。

レベル0のグリッドとは、黒マス１マスからなるグリッドとする。
レベルKのグリッドは、何個の連結マスからなるか。

解法

元のグリッドにおいて、どこかの列で最上段も最下段も黒マスがある列があり、かつどこかの行で最左列も最右列も黒マスがあるのであれば、レベルを増やしてもずっと連結成分は１つ。
よって、以下少なくとも「どこかの列で最上段も最下段も黒マスがある列」がないことを仮定する(そうでない場合は90度回転する)

基本的には、レベルを１増やすと黒マスの数は入力グリッドの黒マス数倍になる。
ただし、以下の条件を満たす左右の隣接マスは、レベルを1上げるため黒マスを入力マスに置き換える際連結する。

• 元々入力マス中で隣接している黒マスは、置換後も隣接する。
• レベルiのマス中で隣接しており、かつ入力マスの各行で最左列と最右列の黒となっている行は、置換後も隣接する。

よって黒マス数・隣接する黒マス数・最左列と最右列が共に黒マスとなっている行数を係数とする2*2行列を考え、(K-1)乗するとよい。

int H,W;
ll K;
string S[1010];
ll mo=1000000007;

void rot() {
	int y,x;
	string T[1010];
	FOR(y,H) FOR(x,W) T[x] += S[y][x];
	FOR(x,1000) S[x]=T[x];
	swap(H,W);
}

const int MAT=2;
ll G[MAT][MAT],G2[MAT][MAT];
void powmat(ll 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(x,n) FOR(z,n) FOR(y,n) h[x][y] += (r[x][z]*a2[z][y]) % mo;
			FOR(x,n) FOR(y,n) r[x][y]=h[x][y]%mo;
		}
		FOR(x,n) FOR(y,n) h[x][y]=0;
		FOR(x,n) FOR(z,n) FOR(y,n) h[x][y] += (a2[x][z]*a2[z][y]) % mo;
		FOR(x,n) FOR(y,n) a2[x][y]=h[x][y]%mo;
		p>>=1;
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W>>K;
	
	FOR(y,H) cin>>S[y];
	int a=0,b=0;
	FOR(y,H) if(S[y][0]=='#' && S[y][W-1]=='#') a++;
	FOR(x,W) if(S[0][x]=='#' && S[H-1][x]=='#') b++;
	if(a&&b) return _P("1\n");
	if(b) rot(), a=b;
	
	FOR(y,H) {
		FOR(x,W) {
			if(S[y][x]=='#') G[0][0]++;
			if(x>0 && a && S[y][x]=='#' && S[y][x-1]=='#') G[0][1]--;
		}
		if(S[y][0]=='#' && S[y][W-1]=='#') G[1][1]++;
	}
	
	G[0][1] += mo;
	
	powmat(K-1,2,G,G2);
	cout<<(G2[0][0] + G2[0][1])%mo<<endl;
	
}

まとめ

これは思いつかんな。