Codeforces Round #313 (Div. 1) C. Gerald and Giant Chess

問題文

http://codeforces.com/contest/559/problem/C

問題概要

H * W のグリッドがある．
このグリッドのうち，ある N マスは使えないようになっている．
この時，左上から右下まで行く方法は何通りあるか．ただし，マスを移動するときは，右または下にしか行けないものとする．

・制約
1 <= H, W <= 10^5
1 <= N <= 2000

解法

まず，与えられた N マスを，左上からのマンハッタン距離で昇順ソートします．
その後，以下のような dp を考えます．
dp[i] := i 番目の使えないマスに一番最初に訪れるような場合の数(訪れたあとの経路は含まない）
すると，遷移は以下のようになります．
dp[i] = comb(x[i] + y[i] - 2, x[i] - 1)) - (i 番目を右下とする領域にあるすべての dp[j] の総和)
左上は (0, 0) でなく (1, 1) であることに気をつける必要があります．

あとは全体から dp[i] * (i 番目から右下まで行く場合の数) を引いてやると，求める答えになります．

ソースコード

#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;
using ll = long long;

constexpr ll M = 1e9 + 7;

ll inv(ll a, ll p) {
    return (a == 1 ? 1 : (1 - p * inv(p % a, a)) / a + p);
}

ll fact(int n, bool inv_) {
    static vector<ll> v1 = {1}, v2 = {1};
    if(n >= (int)v1.size()) {
        int const from = v1.size(), to = n + 1024;
        v1.reserve(to);
        v2.reserve(to);
        for(int i = from; i < to; ++i) {
            v1.push_back(v1.back() * i % M);
            v2.push_back(v2.back() * inv(i, M) % M);
        }
    }
    return inv_ ? v2[n] : v1[n];
}

ll comb(int n, int r) {
    if(r < 0 || r > n) {
        return 1;
    }
    ll res = fact(n, false) * fact(r, true) % M;
    res = res * fact(n - r, true) % M;
    return res;
}

int main() {
    int h, w, n;
    cin >> h >> w >> n;
    vector<pii> v(n);
    for(int i = 0; i < n; ++i) {
        cin >> v[i].first >> v[i].second;
    }
    sort(v.begin(), v.end(), [](auto const& p1, auto const& p2) {
        return p1.first + p1.second < p2.first + p2.second;
    });

    vector<ll> dp(n);
    for(int i = 0; i < n; ++i) {
        int xi = v[i].second;
        int yi = v[i].first;
        dp[i] = comb(xi + yi - 2, yi - 1);
        for(int j = 0; j < i; ++j) {
            int xj = v[j].second;
            int yj = v[j].first;
            if(xi >= xj && yi >= yj) {
                dp[i] = (dp[i] - dp[j] * comb(xi - xj + yi - yj, xi - xj)) % M;
                dp[i] = (dp[i] + M) % M;
            }
        }
    }
    for(int i = 0; i < n; ++i) {
        int x = v[i].second, y = v[i].first;
        dp[i] = (dp[i] * comb(w - x + h - y, w - x)) % M;
    }
    ll res = comb(h + w - 2, h - 1);
    for(int i = 0; i < n; ++i) {
        res = (res - dp[i] + M) % M;
    }

    cout << res << endl;
}

感想

なぜか解けませんでした．猛省．