EDPC Y

https://atcoder.jp/contests/dp/tasks/dp_y

座標をpairに格納してソートしたものをPとする。訪れるマスのPのindexをa_1 < a_2 < a_3 <...< a_mとすると、a_1->a_2->a_3->...->a_mの順番でしか訪問できない。なので、最後に訪れる場所で場合分けできて包除できる。
包除の問題で集合ではなく個数でまとめて持てる場合は、向きをつけられるという特性があるからだと思いました。

int H, W, N;
pi P[MAX_N];
ll dp[MAX_N];

void solve() {
	cin >> H >> W >> N;
	H--; W--;
	rep(i, 0, N) {
		int a, b;
		cin >> a >> b; a--; b--;
		P[i] = pi(a, b);
	}
	sort(P, P + N + 1);
	C_init(H + W);

	rer(i, N + 1, 0) {
		int a = P[i].fst, b = P[i].sec;
		dp[i] = C(H - a + W - b, W - b);
		rep(j, i + 1, N + 1) {
			int c = P[j].fst, d = P[j].sec;
			ADD(dp[i], mod - dp[j] * C(c - a + d - b, d - b) % mod);
		}
		// debug(dp[i], a, b);
	}
	cout << dp[0] << "\n";
}

EDPC埋め完了。でもYが一番むずかしいと思う。