https://atcoder.jp/contests/dp/tasks/dp_y
座標をpair
包除の問題で集合ではなく個数でまとめて持てる場合は、向きをつけられるという特性があるからだと思いました。
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が一番むずかしいと思う。