Codeforces Round #313 (Div. 1) C. Gerald and Giant Chess
問題概要
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; }
感想
なぜか解けませんでした.猛省.