Submission #1871933

---

Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
typedef long long ll ;
#define rep(i, a, b) for (int i = a; i <= b; ++ i) 
const int N = 2005, mo = 1e9 + 7 ;
using namespace std ;
int H, W ; ll k ;
char a[N][N] ;
void upd(int &x, int y) { x = (x + y) % mo ; }
void mul(int A[2][2], int B[2][2], int (&C)[2][2]) {
	rep(i, 0, 1) rep(j, 0, 1) C[i][j] = 0 ;
	rep(i, 0, 1) rep(j, 0, 1) rep(k, 0, 1) upd(C[i][j], (ll) A[i][k] * B[k][j] % mo) ;
}
int ksm(int a, ll b) {
	int ans = 1, w = a % mo ;
	for ( ; b ; b /= 2) {
		if (b & 1LL) ans = (ll) ans * w % mo ;
		w = (ll) w * w % mo ;
	}
	return ans ;
}
int main() {
	scanf("%d%d%lld", &H, &W, &k) ;
	if (k < 2LL) { puts("1") ; return 0 ; } k -= 2 ;
	int tx = 0, ty = 0, w[2][2] = {0}, ans[2][2] = {0}, tmp[2][2], x, y ;
	rep(i, 1, H) scanf("%s", a[i] + 1) ;
	rep(i, 1, H) if (a[i][1] == '#' && a[i][W] == '#') ++ tx ;
	rep(i, 1, W) if (a[1][i] == '#' && a[H][i] == '#') ++ ty ;
	rep(i, 1, H) rep(j, 1, W) if (a[i][j] == '#') ++ w[0][0] ;
	if (tx && ty) { puts("1") ; return 0 ; } 
	if (!tx && !ty) { printf("%d\n", ksm(w[0][0], k - 1)) ; return 0 ; }
	if (tx) {
		rep(i, 1, H) rep(j, 1, W - 1) if (a[i][j] == '#' && a[i][j + 1] == '#') ++ w[0][1] ;
		w[1][1] = tx ;
	} else {
		rep(i, 1, H - 1) rep(j, 1, W) if (a[i][j] == '#' && a[i + 1][j] == '#') ++ w[0][1] ;
		w[1][1] = ty ;
	}
	rep(i, 0, 1) rep(j, 0, 1) ans[i][j] = (i == j) ;
	x = w[0][0], y = w[0][1] ;
	for ( ; k ; k /= 2) {
		if (k & 1LL) {
			mul(ans, w, tmp) ;
			rep(i, 0, 1) rep(j, 0, 1) ans[i][j] = tmp[i][j] ;
		}
		mul(w, w, tmp) ;
		rep(i, 0, 1) rep(j, 0, 1) w[i][j] = tmp[i][j] ;
	}
	int X = (ll) x * ans[0][0] % mo + (ll) y * ans[1][0] % mo ; X %= mo ;
	int Y = (ll) x * ans[0][1] % mo + (ll) y * ans[1][1] % mo ; Y %= mo ;
	printf("%d\n", ((X - Y) % mo + mo) % mo) ;
	return 0 ;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:26:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%lld", &H, &W, &k) ;
                                ^
./Main.cpp:29:37: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  rep(i, 1, H) scanf("%s", a[i] + 1) ;
                                     ^

Judge Result