educational dp contest Y - Grid 2

Y - Grid 2

解法
壁へ行ける事にする。
dp[i] := iへの行き方のうち、他の壁を通らないような場合の数とする。
ここで、ゴール地点gを壁としてやると、dp[g]が答えである。

遷移方法は、iの左上にある任意の壁jで
dp[i] = iへの行き方 - sum(dp[j]からiへ行く方法)となる

Submission #4439088 - Educational DP Contest

vi vh, vw;
digraph<> g(2 * k5);
void solve() {
    cin >> H >> W >> n;
    na2d(vh, vw, n);
    n++;
    vh += H - 1;
    vw += W - 1;
    sortp(vh, vw);
    rep(i, n) {
        rep(j, n) {
            if (i == j)con;
            if (vh[i] <= vh[j] && vw[i] <= vw[j]) {
                g.add(i, j);
            }
        }
    }
    //iに初めて訪れた組み合わせ
    vm dp(k5);
    setMod();
    rep(i, n) {
        int h = vh[i], w = vw[i];
        dp[i] += com(h + w, h);
        forg(gi, g[i]) {
            int dh = vh[t] - h, dw = vw[t] - w;
            dp[t] -= dp[i] * com(dh + dw, dh);
        }
    }
    cout << dp[n - 1] << endl;
}