2012年4月 春コンテスト Problem E: Dungeon Creation (BigInteger.modInverse を使っているのでちょっと邪道) [Licence: NYSL Version 0.9982]

Main.java

import java.util.*;
import java.math.*;

public class Main implements Runnable {
  private static final long MOD = 1000000007;
	private static final BigInteger BMOD = BigInteger.valueOf(MOD);

	private static long inv(final long l) {
		return BigInteger.valueOf(l).modInverse(BMOD).longValue();
	}

	private static final int[] di = { 1, 0, -1, 0 };
	private static final int[] dj = { 0, -1, 0, 1 };

	@Override
	public void run() {
		Scanner sc = new Scanner(System.in);
		for (int c = 1; sc.hasNext(); c++) {
			final int H = sc.nextInt();
			final int W = sc.nextInt();
			if (H == 0 && W == 0)
				return;
			final char[][] map = new char[H][];
			for (int i = 0; i < H; i++)
				map[i] = sc.next().toCharArray();
			System.out.println("Case " + c + ": " + solve(H, W, map));
		}
	}

	private long solve(final int H, final int W, final char[][] map) {
		final int[][] num = new int[H][W];
		int c = 0;
		for (int i = 0; i < H; i++)
			for (int j = 0; j < W; j++)
				if (map[i][j] == '.')
					num[i][j] = c++;
		final long[][] m = new long[c][2 * W + 1];
		for (int i = 0; i < H; i++)
			for (int j = 0; j < W; j++)
				if (map[i][j] == '.')
					for (int d = 0; d < 4; d++)
						if (0 <= i + di[d] && i + di[d] < H && 0 <= j + dj[d] && j + dj[d] < W
								&& map[i + di[d]][j + dj[d]] == '.') {
							m[num[i][j]][num[i + di[d]][j + dj[d]] - num[i][j] + W] = -1l;
							m[num[i][j]][W]++;
						}

		for (int i = 1; i < c; i++) {
			if (m[i][W] == 0l)
				return 0l;
			else {
				long inv = inv(m[i][W]);
				for (int k = W + 1; k <= 2 * W; k++) {
					m[i][k] *= inv;
					m[i][k] %= MOD;
				}
				for (int j = 1; j < Math.min(c - i, W + 1); j++)
					for (int k = 1; k <= W; k++) {
						m[i + j][W - j + k] -= m[i + j][W - j] * m[i][W + k];
						m[i + j][W - j + k] %= MOD;
					}
			}
		}
		long ans = 1l;
		for (int i = 1; i < c; i++) {
			ans *= m[i][W];
			ans %= MOD;
		}
		return (ans + MOD) % MOD;
	}

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

	public static void debug(Object... os) {
		System.err.println(Arrays.deepToString(os));
	}
}