Submission #959727


Source Code Expand

import java.util.*;

public class Main {
	public static void main(String[] args) {
		new Main().run();
	}

	void run() {
		solver();
	}

	final long MODULO = 1_000_000_000 + 7;

	void solver() {
		Scanner sc = new Scanner(System.in);
		int H = sc.nextInt();
		int W = sc.nextInt();
		long K = sc.nextLong();
		char[][] map = new char[H][W];
		for (int i = 0; i < H; ++i) {
			map[i] = sc.next().toCharArray();
		}

		int a = 0;// 黒マスの個数
		int b = 0;// お互いに横でつながっているペアの数
		int c = 0;// 連結な行の数

		for (int i = 0; i < H; ++i) {
			for (int j = 0; j < W; ++j) {
				if (map[i][j] == '#')
					++a;
			}
		}

		for (int i = 0; i < H; ++i) {
			if (map[i][0] == map[i][W - 1] && map[i][0] == '#')
				++c;
		}

		int d = 0;
		for (int i = 0; i < W; ++i) {
			if (map[0][i] == map[H - 1][i] && map[0][i] == '#')
				++d;
		}

		if (c > 0 && d > 0) {
			System.out.println(1);
			return;
		} else if (c == 0 && d == 0) {
			long[][] mx = new long[][] { { a } };
			mx = pow(mx, K - 1);
			System.out.println(mx[0][0]);
			return;
		}

		if (d > 0) {
			map = rev(map);
			c = d;
			d = 0;
			int tmp = H;
			H = W;
			W = tmp;
		}

		for (int i = 0; i < H; ++i) {
			for (int j = 0; j < W - 1; ++j) {
				if (map[i][j] == map[i][j + 1] && map[i][j] == '#') {
					++b;
				}
			}
		}

		long[][] mx = new long[][] { { a, -b }, { 0, c } };
		long[][] v = new long[][] { { 1 }, { 1 } };
		mx = pow(mx, K - 1);
		v = mul(mx, v);
		System.out.println(v[0][0]);

	}

	long[][] mul(long[][] a, long[][] b) {
		long[][] ret = new long[a.length][b[0].length];

		for (int i = 0; i < b[0].length; ++i) {
			for (int j = 0; j < a.length; ++j) {
				for (int k = 0; k < a[0].length; ++k) {
					ret[j][i] += a[j][k] * b[k][i] % MODULO;
					ret[j][i] = (ret[j][i] + MODULO) % MODULO;
				}

			}
		}
		return ret;
	}

	long[][] pow(long[][] a, long n) {
		int len = a.length;
		long[][] ret = new long[len][len];
		for (int i = 0; i < len; ++i) {
			ret[i][i] = 1;
		}
		for (; n > 0; n >>= 1, a = mul(a, a)) {
			if (n % 2 == 1)
				ret = mul(a, ret);
		}
		return ret;
	}

	char[][] rev(char[][] map) {
		char[][] ret = new char[map[0].length][map.length];
		for (int i = 0; i < map.length; ++i) {
			for (int j = 0; j < map[0].length; ++j) {
				ret[j][i] = map[i][j];
			}
		}
		return ret;
	}

	void showMap(char[][] map) {
		int H = map.length;
		int W = map[0].length;
		for (int i = 0; i < H; ++i) {
			for (int j = 0; j < W; ++j) {
				System.out.print(map[i][j] + " ");
			}
			System.out.println();
		}
	}

	void tr(Object... o) {
		System.out.println(Arrays.deepToString(o));
	}
}

Submission Info

Submission Time
Task F - Fraction of Fractal
User fortoobye
Language Java8 (OpenJDK 1.8.0)
Score 1700
Code Size 2765 Byte
Status AC
Exec Time 310 ms
Memory 23900 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1700 / 1700
Status
AC × 3
AC × 47
Set Name Test Cases
Sample s1.txt, s2.txt, s3.txt
All 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, s1.txt, s2.txt, s3.txt
Case Name Status Exec Time Memory
01.txt AC 263 ms 21732 KB
02.txt AC 288 ms 21560 KB
03.txt AC 297 ms 23708 KB
04.txt AC 291 ms 21636 KB
05.txt AC 299 ms 23556 KB
06.txt AC 285 ms 21372 KB
07.txt AC 268 ms 20540 KB
08.txt AC 282 ms 21632 KB
09.txt AC 281 ms 21264 KB
10.txt AC 308 ms 23532 KB
11.txt AC 303 ms 22056 KB
12.txt AC 293 ms 21864 KB
13.txt AC 280 ms 21672 KB
14.txt AC 277 ms 20772 KB
15.txt AC 288 ms 20692 KB
16.txt AC 279 ms 21580 KB
17.txt AC 284 ms 21968 KB
18.txt AC 282 ms 21348 KB
19.txt AC 282 ms 21296 KB
20.txt AC 298 ms 23264 KB
21.txt AC 308 ms 23900 KB
22.txt AC 281 ms 21776 KB
23.txt AC 300 ms 23492 KB
24.txt AC 296 ms 22620 KB
25.txt AC 298 ms 22892 KB
26.txt AC 291 ms 21576 KB
27.txt AC 310 ms 23536 KB
28.txt AC 290 ms 21568 KB
29.txt AC 124 ms 9804 KB
30.txt AC 125 ms 9676 KB
31.txt AC 125 ms 9684 KB
32.txt AC 126 ms 9680 KB
33.txt AC 126 ms 9680 KB
34.txt AC 125 ms 9672 KB
35.txt AC 127 ms 9676 KB
36.txt AC 129 ms 9680 KB
37.txt AC 127 ms 9676 KB
38.txt AC 126 ms 9672 KB
39.txt AC 126 ms 9680 KB
40.txt AC 126 ms 9552 KB
41.txt AC 125 ms 9676 KB
42.txt AC 127 ms 9676 KB
43.txt AC 126 ms 9676 KB
44.txt AC 126 ms 9676 KB
s1.txt AC 126 ms 9668 KB
s2.txt AC 125 ms 9556 KB
s3.txt AC 128 ms 9680 KB