AGC003F

https://agc003.contest.atcoder.jp/tasks/agc003_f

非連結だと勘違いしてハマってた…

まず縦に並べても横に並べても繋がる場合は答えが1です。
どっちもつながらない場合は#の個数をPとしてP^(K-1)です。
問題は片方だけ繋がる場合です。今回は横に繋がるとします。
#が横に２つ連続で繋がるものの個数をen、連結成分の数をfnとします。
また、盤面を横に並べた時#が繋がる個数をDとします。
するとen+1とfn+1はPとDの線形和で表されます。後は行列累乗をO(logK)でやれば答えが求まります。

ただH=1とW=1の時は場合分けが発生するので注意しましょう。

void solve() {
	cin >> H >> W >> K;
	ll p = 0;
	rep(i, 0, H) {
		string str;
		cin >> str;
		rep(j, 0, W) {
			if(str[j] == '#') B[i][j] = 1;
			p += B[i][j];
		}
	}
	int bh = 0, bw = 0;
	rep(j, 0, W) {
		if(B[0][j] == 1 && B[H - 1][j] == 1) bh++;
	}
	rep(i, 0, H) {
		if(B[i][0] == 1 && B[i][W - 1] == 1) bw++;
	}
	if(H == 1) {
		if(bw) cout << 1 << "\n";
		else cout << mod_pow(p, K - 1) << "\n";
	}
	else if(W == 1) {
		if(bh) cout << 1 << "\n";
		else cout << mod_pow(p, K - 1) << "\n";
	}
	else {
		if(bw && bh) {
			cout << 1 << "\n";
		}
		else if(!bw && !bh) {
			cout << mod_pow(p, K - 1) << "\n";
		}
		else {
			int e = 0;
			int f;
			if(bh) {
				rep(i, 0, H - 1) {
					rep(j, 0, W) {
						if(B[i][j] == 1 && B[i + 1][j] == 1) e++;
					}
				}
				f = bh;
			}
			else {
				rep(j, 0, W - 1) {
					rep(i, 0, H) {
						if(B[i][j] == 1 && B[i][j + 1] == 1) e++;
					}
				}
				f = bw;
			}
			// debug(bh, bw, p, e);
			mat A(2, vl(2, 0));
			A[0][0] = p;
			A[0][1] = mod - 1;
			A[1][0] = 0;
			A[1][1] = f;
			mat B = mat_pow(A, K - 1);
			cout << (B[0][0] + B[0][1] * e % mod) % mod << "\n";
		}
	}
}

なんか割と非連結でもいけそうな雰囲気が漂っていたから誤読に全然気づかなかった…。
多分問題数もっと解けばできるできないの判断が鋭くなるんだろうな…