Codeforces Round #313 Div1 C: Gerald and Giant Chess

問題

codeforces.com

解法

包除原理を使う。

各障害物のセルとゴールのセルに、

(スタートからの経路数)-(障害物を1つ通る経路数)+(障害物を2つ通る経路数)-(障害物を3つ通る経路数)-...

を記録するようにすれば良い。

コード

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main {
	public final int MAX = 200000;
	public final long MOD = 1000000007;

	public void solve() {

		long[] fact = Mod.factorialArray(MAX, MOD);
		long[] factInv = Mod.factorialInverseArray(MAX, MOD,
				Mod.inverseArray(MAX, MOD));

		Scanner scanner = new Scanner(System.in);
		int H = scanner.nextInt();
		int W = scanner.nextInt();
		int N = scanner.nextInt();

		ArrayList<Cell> cells = new ArrayList<>();
		cells.add(new Cell(1, 1));
		cells.add(new Cell(H, W));
		for (int i = 0; i < N; i++) {
			int x = scanner.nextInt();
			int y = scanner.nextInt();
			cells.add(new Cell(x, y));
		}
		scanner.close();
		/*
		 * 各障害物セルに-(スタートからの経路)+(障害物を1回通る経路)-(2回通る経路)+(3回通る経路)-... が保存されている
		 */

		Collections.sort(cells);
		cells.get(0).pathes = 1;
		for (int i = 1; i < cells.size(); i++) {
			Cell target = cells.get(i);
			for (int j = 0; j < i; j++) {
				Cell prev = cells.get(j);
				if (prev.r > target.r || prev.c > target.c) {
					// prevからtargetに行き得ない時はスルー
					continue;
				}

				int dr = target.r - prev.r;
				int dc = target.c - prev.c;

				// prevからtargetへの経路数
				long pathes = fact[dr + dc] % MOD * factInv[dr] % MOD
						* factInv[dc] % MOD;

				target.pathes -= prev.pathes * pathes;
				target.pathes += MOD;
				target.pathes %= MOD;
			}
		}

		long ans = -cells.get(cells.size() - 1).pathes;
		while (ans < 0) {
			ans += MOD;
		}
		ans %= MOD;
		System.out.println(ans);
	}

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

}

class Cell implements Comparable<Cell> {
	int r, c;
	long pathes;

	public Cell(int i, int j) {
		this.r = i;
		this.c = j;
		this.pathes = 0;
	}

	public int compareTo(Cell o) {
		return Integer.compare(this.r + this.c, o.r + o.c);
	}

}

// Mod系ライブラリ
class Mod {
	public static long n(long x, long mod) {
		x %= mod;
		if (x < 0) {
			x += mod;
		}
		return x;
	}

	public static long inverse(long a, long mod) {
		long b = mod, u = 1, v = 0;
		while (b > 0) {
			long temp;
			long t = a / b;
			a -= t * b;
			temp = a;
			a = b;
			b = temp;
			u -= t * v;
			temp = u;
			u = v;
			v = temp;
		}
		return (u % mod + mod) % mod;
	}

	public static long[] inverseArray(int maxN, long modP) {
		long[] inv = new long[maxN + 1];
		inv[1] = 1;
		for (int i = 2; i <= maxN; i++) {
			inv[i] = modP - (modP / i) * inv[(int) (modP % i)] % modP;
		}
		return inv;
	}

	// maxN!の数列を返す　
	public static long[] factorialArray(int maxN, long mod) {
		long[] fact = new long[maxN + 1];
		fact[0] = 1 % mod;
		for (int i = 1; i <= maxN; i++) {
			fact[i] = fact[i - 1] * i % mod;
		}
		return fact;
	}

	// 1/(maxN!)のmodinverseを返す
	public static long[] factorialInverseArray(int maxN, long modP,
			long[] inverseArray) {
		long[] factInv = new long[maxN + 1];
		factInv[0] = 1;
		for (int i = 1; i <= maxN; i++) {
			factInv[i] = factInv[i - 1] * inverseArray[i] % modP;
		}
		return factInv;
	}
}