Submission #5075702

---

Source Code Expand

#include <bits/stdc++.h>
// iostream is too mainstream
#include <cstdio>
// bitch please
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <cmath>
#include <iomanip>
#include <time.h>
#define dibs reserve
#define OVER9000 1234567890
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
#define tisic 47
#define soclose 1e-8
#define chocolate win
// so much chocolate
#define patkan 9
#define ff first
#define ss second
#define abs(x) (((x) < 0)?-(x):(x))
#define uint unsigned int
#define dbl long double
#define pi 3.14159265358979323846
using namespace std;
// mylittledoge

using cat = long long;

#ifdef DONLINE_JUDGE
	// palindromic tree is better than splay tree!
	#define lld I64d
#endif

cat pw(cat a, cat e, cat mod) {
	if(e <= 0) return 1;
	cat x = pw(a, e/2, mod);
	x = x * x % mod;
	if(e & 1) x = x * a % mod;
	return x;
}

vector< vector<cat> > prod(vector< vector<cat> > & A, vector< vector<cat> > & B, cat mod) {
	int N = A.size();
	vector< vector<cat> > C(N, vector<cat>(N, 0));
	for(int i = 0; i < N; i++) for(int j = 0; j < N; j++) {
		for(int k = 0; k < N; k++) C[i][j] += A[i][k] * B[k][j] % mod;
		C[i][j] %= mod;
	}
	return C;
}

vector< vector<cat> > pw_mat(vector< vector<cat> > & A, cat e, cat mod) {
	int N = A.size();
	if(e <= 0) {
		vector< vector<cat> > ret(N, vector<cat>(N, 0));
		for(int i = 0; i < N; i++) ret[i][i] = 1;
		return ret;
	}
	vector< vector<cat> > x = pw_mat(A, e/2, mod);
	x = prod(x, x, mod);
	if(e & 1) x = prod(x, A, mod);
	return x;
}

int main() {
	cin.sync_with_stdio(0);
	cin.tie(0);
	cout << fixed << setprecision(10);
	int H, W;
	cat K, mod = 1000000007;
	cin >> H >> W >> K;
	if(K <= 1) {
		cout << "1\n";
		return 0;
	}
	vector<string> S(H);
	for(int i = 0; i < H; i++) cin >> S[i];
	bool conn_h = false, conn_w = false;
	for(int i = 0; i < H; i++)
		if(S[i][0] == '#' && S[i][W-1] == '#') conn_w = true;
	for(int i = 0; i < W; i++)
		if(S[0][i] == '#' && S[H-1][i] == '#') conn_h = true;
	if(conn_h && conn_w) {
		cout << "1\n";
		return 0;
	}
	if(!conn_h && !conn_w) {
		cat cnt = 0;
		for(int i = 0; i < H; i++) for(int j = 0; j < W; j++)
			if(S[i][j] == '#') cnt++;
		cat ans = pw(cnt, K-1, mod);
		cout << ans << "\n";
		return 0;
	}
	vector<int> seg0;
	vector< pair<int, int> > seg1;
	int seg2 = 0;
	if(conn_h) {
		vector<string> St(W);
		for(int i = 0; i < H; i++) for(int j = 0; j < W; j++)
			St[j] += S[i][j];
		S = St;
		swap(H, W);
	}
	for(int i = 0; i < H; i++) {
		int l0 = 0, r0 = 0;
		if(S[i][0] == '#' && S[i][W-1] == '#') {
			for(int j = 0; j < W; j++) {
				if(S[i][j] == '.') break;
				l0++;
			}
			for(int j = W-1; j >= 0; j--) {
				if(S[i][j] == '.') break;
				r0++;
			}
			if(l0 == W) {
				seg2++;
				continue;
			}
			seg1.push_back({l0, r0});
		}
		int l = -1;
		for(int j = 0; j < W; j++) {
			if(S[i][j] == '#') continue;
			if(l != j-1)
				if(l != -1 || (S[i][0] == '.' || S[i][W-1] == '.'))
					seg0.push_back(j-1-l);
			l = j;
		}
		if(l != W-1) 
			if(S[i][0] == '.' || S[i][W-1] == '.') seg0.push_back(W-1-l);
	}
	map<int, int> L;
	L[1] = L[W] = 0;
	ALL_THE(seg0, it) L[*it] = 0;
	ALL_THE(seg1, it) {
		L[it->ff] = 0;
		L[it->ss] = 0;
		L[it->ff+it->ss] = 0;
	}
	int NL = 0;
	ALL_THE(L, it) it->ss = NL++;
	vector< vector<cat> > M(NL+2, vector<cat>(NL+2, 0));
	ALL_THE(L, it) {
		ALL_THE(seg0, jt) M[L[*jt]][it->ss] += it->ff;
		ALL_THE(seg1, jt) {
			M[L[jt->ff+jt->ss]][it->ss] += it->ff-1;
			M[L[jt->ff]][it->ss] += 1;
			M[L[jt->ss]][it->ss] += 1;
		}
		M[NL][it->ss] += seg2;
		M[NL+1][it->ss] = 1LL * seg2 * W * it->ff % mod;
	}
	ALL_THE(seg0, jt) M[L[*jt]][NL+1]++;
	ALL_THE(seg1, jt) {
		M[L[jt->ff+jt->ss]][NL+1]++;
		M[L[jt->ff+jt->ss]][NL]--;
		M[L[jt->ff]][NL]++;
		M[L[jt->ss]][NL]++;
	}
	M[NL][NL] += seg2;
	M[NL+1][NL+1] += W * seg2;
	/* n_l = n; l < W:
		n'_(seg0[i]) += l*n
		n'_(seg1[i]) += l*n
		n'_(seg1[i]) -= n
		n'_(segl[i]) += n
		n'_(segr[i]) += n
		n_(l >= W)   += seg2*n
		s_(l >= W)   += seg2*n*W*l

	   n_(l >= W) = n, sum_(l >= W) = s:
		n'_(seg0[i]) += s
		n'_(seg1[i]) += s
		n'_(seg1[i]) -= n
		n'_(segl[i]) += n
		n'_(segr[i]) += n
		n            += seg2*n
		s            += W*seg2*s
	*/
	vector< vector<cat> > MP = pw_mat(M, K-1, mod);
	cat ans = 0;
	for(int i = 0; i <= NL; i++) ans += MP[i][0];
	ans %= mod;
	if(ans < 0) ans += mod;
	cout << ans << "\n";
	return 0;
}

// look at my code
// my code is amazing

Submission Info

Judge Result