mayoko’s diary

プロコンとかいろいろ。

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

本番は筋の悪い方法で考え込んでしまった。

解法

最近流行り(?)の包除原理で解けます。

解法の流れとしては,障害物をp個以上通る経路の数をf(p)とすると,求める経路の数は

f(0) - f(1) + f(2) - ...

で求めることが出来るので,それを利用する感じです。包除原理を素直に使うとO(2^n)でダメですが,プラスマイナスを決める大事なファクターは「いくつの障害物を通ることが確定しているかの偶奇」のみであることに着目すると,dp[n][flag] = (今までに通ることが確定している障害物の数の偶奇がflagで表され,n個目の障害物の上を通っている時の場合の数)でdpになります。

const int MAXH = 200200;
const int MAXN = 2222;
const ll MOD = 1e9+7;
ll fact[MAXH];
ll factr[MAXH];
pii block[MAXN];
ll dp[MAXN][2];
int h, w, n;

// extgcd
ll extgcd(ll a, ll b, ll& x, ll& y) {
    ll d = a;
    if (b != 0) {
        d = extgcd(b, a % b, y, x);
        y -= (a / b) * x;
    } else {
        x = 1; y = 0;
    }
    return d;
}

// mod_inverse
ll mod_inverse(ll a, ll m) {
    ll x, y;
    extgcd(a, m, x, y);
    return (m+x%m) % m;
}

ll nCr(int n, int r) {
    ll ret = fact[n];
    (ret *= factr[r]) %= MOD;
    (ret *= factr[n-r]) %= MOD;
    return ret;
}

ll dfs(int cur, int eo) {
    if (cur == n+1) {
        if (eo == 0) return 1;
        else return -1;
    }
    ll& ret = dp[cur][eo];
    if (ret >= 0) return ret;
    ret = 0;
    for (int i = cur+1; i <= n+1; i++) {
        //if (i == cur) continue;
        int dx = block[i].first - block[cur].first;
        int dy = block[i].second - block[cur].second;
        if (dx < 0 || dy < 0) continue;
        int neo = eo;
        if (i < n+1) neo ^= 1;
        ret += nCr(dx+dy, dx) * dfs(i, neo);
        ret %= MOD;
    }
    if (ret < 0) ret += MOD;
    return ret;
}


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    fact[0] = 1;
    factr[0] = 1;
    for (int i = 1; i < MAXH; i++) {
        fact[i] = (i*fact[i-1]) % MOD;
        factr[i] = mod_inverse(fact[i], MOD);
    }
    cin >> h >> w >> n;
    block[0].first = 0, block[0].second = 0;
    for (int i = 1; i <= n; i++) {
        cin >> block[i].first >> block[i].second;
        block[i].first--; block[i].second--;
    }
    block[n+1].first = h-1; block[n+1].second = w-1;
    sort(block, block+n+2);
    memset(dp, -1, sizeof(dp));
    cout << dfs(0, 0) << endl;
    return 0;
}