Submission #847881

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

#define forn(i, a, n) for (int i = a; i < n; ++i)
#define ford(i, a, n) for (int i = n - 1; i >= a; --i)
#define fore(i, a, n) for (int i = a; i <= n; ++i)
#define all(a) (a).begin(), (a).end()
#define fs first
#define sn second
#define trace(a)\
	for (auto i : a) cerr << i << ' ';\
	cerr << '\n'
#define eb emplace_back

#ifndef M_PI
const ld M_PI = acos(-1.0);
#endif

const ld eps = 1e-9;
const int INF = 2000000000;
const ll LINF = 1ll * INF * INF;
const ll MOD = 1000000007;

struct Matrix {
	ll a[2][2];

	Matrix () {};

	Matrix (int cells, int inBound, int outBound) {
		a[0][0] = cells;
		a[0][1] = -inBound;
		if (a[0][1] < 0) a[0][1] += MOD;
		a[1][0] = 0;
		a[1][1] = outBound;
	}

	Matrix operator* (Matrix other) {
		Matrix m(0, 0, 0);
		forn(i, 0, 2) forn(j, 0, 2) forn(k, 0, 2) {
			m.a[i][k] += a[i][j] * other.a[j][k];
			m.a[i][k] %= MOD;
		}
		return m;
	}

	Matrix Pow (ll k) {
		Matrix x = *this, y = Matrix(1, 0, 1);
		while (k) {
			if (k % 2) y = x * y;
			x = x * x;
			k /= 2;
		}
		return y;
	}
};

ll Pow (ll n, ll k) {
	ll x = n, y = 1;
	while (k) {
		if (k % 2) y = y * x % MOD;
		x = x * x % MOD;
		k /= 2;
	}
	return y;
}

const int N = 1002;
char a[N][N];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int h, w;
	ll k;
	cin >> h >> w >> k;
	if (k <= 1) {
		cout << "1\n";
		return 0;
	}
	forn(i, 0, h) forn(j, 0, w) cin >> a[i][j];
	bool ver = false, hor = false;
	forn(i, 0, h) if (a[i][0] == '#' && a[i][w - 1] == '#') hor = true;
	forn(i, 0, w) if (a[0][i] == '#' && a[h - 1][i] == '#') ver = true;
	if (hor && ver) {
		cout << "1\n";
		return 0;
	}
	int sz = 0;
	forn(i, 0, h) forn(j, 0, w) if (a[i][j] == '#') ++sz;
	if (!hor && !ver) {
		cout << Pow(sz, k - 1) << '\n';
		return 0;
	}
	if (ver) {
		forn(i, 0, N) forn(j, 0, i) swap(a[i][j], a[j][i]);
		swap(h, w);
	}
	int in = 0;
	forn(i, 0, h) forn(j, 0, w - 1) if (a[i][j] == '#' && a[i][j + 1] == '#') ++in;
	int out = 0;
	forn(i, 0, h) if (a[i][0] == '#' && a[i][w - 1] == '#') ++out;
	Matrix M = Matrix(sz, in, out);
	Matrix P = M.Pow(k - 1);
	cout << (P.a[0][0] + P.a[0][1]) % MOD << '\n';
	return 0;
}

Submission Info

Judge Result