Submission #1871857

---

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, flg[4][2] = {{1, 0}, {0, 1}, {- 1, 0}, {0, - 1}} ;
using namespace std ;
int H, W ;
char a[N][N] ; bool vis[N][N] ;
struct poi { int x, y ; } opt[N * N] ;
void upd(int &x, int y) { x = (x + y) % mo ; }
void mul(int A[4][4], int B[4][4], int (&C)[4][4]) {
	rep(i, 0, 3) rep(j, 0, 3) C[i][j] = 0 ;
	rep(i, 0, 3) rep(j, 0, 3) rep(k, 0, 3) upd(C[i][j], (ll) A[i][k] * B[k][j] % mo) ;
}
void bfs(int x, int y, int n, int m) {
	int he = 0, ta = 1 ;
	opt[1].x = x, opt[1].y = y, vis[x][y] = false ;
	for ( ; he != ta ; ) {
		++ he ; int x = opt[he].x, y = opt[he].y ;
		rep(i, 0, 3) {
			int xx = x + flg[i][0], yy = y + flg[i][1] ;
			if (xx < 1 || xx > n || yy < 1 || yy > m || !vis[xx][yy] || a[xx][yy] != '#') continue ;
			vis[xx][yy] = false, ++ ta, opt[ta].x = xx, opt[ta].y = yy ;
		}
	}
}
int count(int n, int m) {
	int res = 0 ;
	rep(i, 1, n) rep(j, 1, m) vis[i][j] = true ;
	rep(i, 1, n) rep(j, 1, m) if (vis[i][j] && a[i][j] == '#') ++ res, bfs(i, j, n, m) ;
	return res ;
}
void calc(int &sum, int &x, int &y, int &z) {
	sum = 0, x = 0, y = 0, z = 0 ;
	rep(i, 1, H) rep(j, 1, W) if (a[i][j] == '#') {
		if (a[i - 1][j] == '#') {
			if (a[i][j - 1] == '#') ++ z ; else ++ y ;
		} else {
			if (a[i][j - 1] == '#') ++ x ; else ++ sum ;
		}
	}
}
int main() {
	int ans[4][4], w[4][4], tmp[4][4] ; ll k ;
	scanf("%d%d%lld", &H, &W, &k) ;
	rep(i, 1, 2 * H) rep(j, 1, 2 * W) a[i][j] = '.' ;
	if (!k) { puts("1") ; return 0 ; } -- k ;
	rep(i, 1, H) scanf("%s", a[i] + 1) ;
	rep(i, 0, 3) rep(j, 0, 3) w[i][j] = ans[i][j] = 0 ;
	rep(i, 0, 3) ans[i][i] = 1 ;
	int sum, x, y, z ;
	calc(sum, x, y, z), w[0][0] = sum, w[1][0] = x, w[2][0] = y, w[3][0] = z ;
	rep(i, 1, H) a[i][0] = a[i][W] ;
	calc(sum, x, y, z), w[0][1] = sum, w[1][1] = x, w[2][1] = y, w[3][1] = z ;
	rep(i, 1, H) a[i][0] = '.' ;
	rep(i, 1, W) a[0][i] = a[H][i] ;
	calc(sum, x, y, z), w[0][2] = sum, w[1][2] = x, w[2][2] = y, w[3][2] = z ;
	rep(i, 1, H) a[i][0] = a[i][W] ;
	calc(sum, x, y, z), w[0][3] = sum, w[1][3] = x, w[2][3] = y, w[3][3] = z ;
	for ( ; k ; k /= 2LL) {
		if (k & 1LL) {
			mul(ans, w, tmp) ;
			rep(i, 0, 3) rep(j, 0, 3) ans[i][j] = tmp[i][j] ;
		}
		mul(w, w, tmp) ;
		rep(i, 0, 3) rep(j, 0, 3) w[i][j] = tmp[i][j] ;
	}
	int res = 0, u = count(H * 2, W * 2), las = u ;
	upd(res, (ll) u * ans[0][0] % mo) ;
	rep(i, 1, H) rep(j, 1, W) a[i][j + W] = a[i][j] ;
	u = count(H * 2, W * 2) ;
	upd(res, (ll) (u - las) * ans[1][0] % mo) ;
	rep(i, 1, H) rep(j, 1, W) a[i][j + W] = '.', a[i + H][j] = a[i][j] ;
	u = count(H * 2, W * 2) ;
	upd(res, (ll) (u - las) * ans[2][0] % mo) ;
	rep(i, 1, H) rep(j, 1, W) a[i][j + W] = a[i][j] ;
	las = count(H * 2, W * 2) ;
	rep(i, 1, H) rep(j, 1, W) a[i + H][j + W] = a[i][j] ;
	u = count(H * 2, W * 2) ;
	upd(res, (ll) (u - las) * ans[3][0] % mo) ;
	printf("%d\n", (res + mo) % mo) ;
	return 0 ;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:48: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:51: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