Codeforces Round #313 (Div. 1) C. Gerald and Giant Chess
本番は筋の悪い方法で考え込んでしまった。
解法
最近流行り(?)の包除原理で解けます。
解法の流れとしては,障害物をp個以上通る経路の数をf(p)とすると,求める経路の数は
f(0) - f(1) + f(2) - ...
で求めることが出来るので,それを利用する感じです。包除原理を素直に使うとでダメですが,プラスマイナスを決める大事なファクターは「いくつの障害物を通ることが確定しているかの偶奇」のみであることに着目すると,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; }