Submission #1386913

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll maxx = 1e3 + 20, mod = 1e9 + 7;

char t[maxx][maxx];
ll n, m, k, ted = 0, c1 = 0, e, c2 = 0, mat[2][2], tmp[2][2];
bool b1 = false, b2 = false;
vector<ll> v;

ll pw(ll a, ll b)
{
	if (!b) return 1ll;
	ll x = pw(a, b / 2);
	x = (x * x) % mod;
	if (b % 2) x = (x * a) % mod;
	return x;
}

void zrb(ll t1[][2], ll t2[][2])
{
	ll t3[2][2] = {{0, 0}, {0, 0}};
	for(ll i = 0; i < 2; i++)
		for(ll j = 0; j < 2; j++)
			for(ll o = 0; o < 2; o++)
				t3[i][j] = (((t3[i][j] + ((t1[i][o] * t2[o][j]) % mod)) % mod) + mod) % mod;
	for(ll i = 0; i < 2; i++)
		for(ll j = 0; j < 2; j++)
			mat[i][j] = t3[i][j];
}

void pw(ll x)
{
	if (x == 1) return;
	while (x >= 1) 
	{
		v.push_back(x);
		x /= 2;
	}
	reverse(v.begin(), v.end());
	x = 1;
	for(ll i = 1; i < v.size(); i++)
	{
		x *= 2ll;
		zrb(mat, mat);
		if (x != v[i]) x++, zrb(mat, tmp);
	}
	return;
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> m >> k;
	for(ll i = 0; i < n; i++) for(ll j = 0; j < m; j++) cin >> t[i][j], ted += (t[i][j] == '#');
	if (!k) return cout << 1 << endl, 0;
	for(ll i = 0; i < n; i++) if (t[i][0] == '#' && t[i][m-1] == '#') b1 = true, c1++;
	for(ll i = 0; i < m; i++) if (t[0][i] == '#' && t[n-1][i] == '#') b2 = true, c2++;
	if (b1 && b2) return cout << 1 << endl, 0; 
	if (!b1 && !b2) while (true) cout << 0 / 0 << endl;//return cout << pw(ted, k - 1) << endl, 0;
	if (b1)
	{
		for(ll i = 0; i < n; i++) for(ll j = 0; j < m - 1; j++) if (t[i][j] == '#' && t[i][j + 1] == '#') e++;
		mat[0][0] = ted; mat[0][1] = -e; mat[1][0] = 0; mat[1][1] = c1;
		tmp[0][0] = ted; tmp[0][1] = -e; tmp[1][0] = 0; tmp[1][1] = c1;
		pw(k - 1);
		return cout << (((mat[0][0] + mat[0][1]) % mod) + mod) % mod << endl, 0;
	}
	else
	{
		for(ll i = 0; i < n - 1; i++) for(ll j = 0; j < m; j++) if (t[i][j] == '#' && t[i + 1][j] == '#') e++;
		mat[0][0] = ted; mat[0][1] = -e; mat[1][0] = 0; mat[1][1] = c2;
		tmp[0][0] = ted; tmp[0][1] = -e; tmp[1][0] = 0; tmp[1][1] = c2;
		pw(k - 1);
		return cout << (((mat[0][0] + mat[0][1]) % mod) + mod) % mod << endl, 0;
	}
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:63:41: warning: division by zero [-Wdiv-by-zero]
  if (!b1 && !b2) while (true) cout << 0 / 0 << endl;//return cout << pw(ted, k - 1) << endl, 0;
                                         ^

Judge Result