EDPC Y : Grid 2 - Lilliput Steps

問題文：https://atcoder.jp/contests/dp/tasks/dp_y

概要

日本語なので略。

解法

「1つも壁を通らない経路の個数」は、「全体の経路の個数」から「壁を1つ以上通る経路の個数」を引くことで求められる。

全体の経路の個数
全体の経路の個数は $\displaystyle{\binom{W+H}{W}}$ となる。

壁を1つ以上通る経路の個数
壁マス全体の集合を $A$ とする。また、任意の $A$ の部分集合 $S$ について、

$f(S) :=$ $(1, 1)$ から $S$ に含まれる壁をすべて通って $(H, W)$ にたどり着く経路の個数
とする。すると、包除原理より壁を1つ以上通る経路の個数は $\displaystyle{\sum_{\emptyset \subsetneq S \subseteq A} (-1)^{|S|-1} f(S)}$ で求まる。

上記をまとめると、結局「1つも壁を通らない経路の個数」は $\displaystyle{\sum_{S \subseteq A} (-1)^{|S|} f(S)}$ と表される事がわかる。

よって、この包除原理の式の各項を計算していけば答えが求まる。しかし、項の個数は $2^N$ 個あるため、愚直に計算するのではなく効率的に和の計算を行う必要がある。

半順序関係の導入
ここで先程の $f(S)$ を思い出してみよう。次の図のような関係にある壁がどちらも $S$ に含まれている場合、今回の問題設定では右と下方向にしか動けないため $f(S) = 0$ となる。

f:id:kagamiz:20200402191600p:image:w200 — $f(S) = 0$ となる壁マスの配置の例

$f(S) = 0$ となる $S$ は求めたい和を変えないため、そうでない $S$ について考察してみよう。
$f(S) \neq 0$ となるためには、 $|S|$ 個の壁マスが「左上から右下に並んでいる」必要がある。

もう少し厳密に書くと、 $\mathbb{N} \times \mathbb{N}$ に半順序関係

$(r_1, c_1) \preceq (r_2, c_2) \overset{\rm{def}}{\iff} r_1 \leqq r_2$ かつ $c_1 \leqq c_2$

を導入したときに、 $f(S) \neq 0$ となるためには $S$ の元だけで考えたときに $\preceq$ が全順序になっている必要がある。この順序をもとに動的計画法の式を立式することを考える。

動的計画法の遷移式の立式

壁マスと $(1, 1), (H, W)$ からなる集合 $B$ を考える。任意の $B$ のマス $(r, c) \in B$ について

$g(r, c) :=$ ( $(1, 1)$ から $(r, c)$ まで偶数個の壁マスをたどって到達する方法の個数)
$h(r, c) :=$ ( $(1, 1)$ から $(r, c)$ まで奇数個の壁マスをたどって到達する方法の個数)

とする*1。このとき、上記の定義より、漸化式

$g(1, 1) = 1$
$h(1, 1) = 0$
$\displaystyle{g(r, c) = \sum_{\{(r', c') \mid (r', c') \in B \setminus \{ (r, c) \}, (r', c') \preceq (r, c)\}} \binom{r - r' + c - c'}{r - r'} h(r', c')}$
$\displaystyle{h(r, c) = \sum_{\{(r', c') \mid (r', c') \in B \setminus \{ (r, c) \}, (r', c') \preceq (r, c)\}} \binom{r - r' + c - c'}{r - r'} g(r', c')}$

が成り立つ。
また、「1つも壁を通らない経路の個数」 $\displaystyle{\sum_{S \subseteq A} (-1)^{|S|} f(S)}$ は $h(H, W) - g(H, W)$ で求まる。

上記の漸化式は $B$ に属するマスを適切な順序で並び替えることにより計算することが可能である。
あるマスについて、順序関係がある別のマスの個数は $\mathrm{O}(N)$ 個ある。
$B$ の元は $O(N)$ 個存在する。したがって $\mathrm{O}(N^2)$ 時間でこの問題を解くことができる。

コード

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX_SIZE = 200000;
const int MAX_N    = 3000;
const int MOD      = 1000000007;

typedef long long Int;

Int fac[MAX_SIZE + 1];
Int inv[MAX_SIZE + 1], ifac[MAX_SIZE + 1];

Int comb(int n, int r)
{
  Int ret = fac[n];
  ret = (ret * ifac[r]) % MOD;
  ret = (ret * ifac[n - r]) % MOD;
  return ret;
}

Int dp[MAX_N + 2][2];

int main()
{
  int h, w, n;
  scanf("%d %d %d", &h, &w, &n);
  
  inv[1] = 1;
  fac[0] = ifac[0] = 1;
  fac[1] = ifac[1] = 1;
  for (int i = 2; i <= h + w; i++) {
    fac[i] = (fac[i - 1] * i) % MOD;
    inv[i] = (inv[MOD % i] * (MOD - MOD / i)) % MOD;
    ifac[i] = ifac[i - 1] * inv[i] % MOD;
  }
  
  vector< pair<int, int> > pos;
  pos.push_back(make_pair(1, 1));
  pos.push_back(make_pair(h, w));
  for (int i = 0; i < n; i++) {
    int r, c;
    scanf("%d %d", &r, &c);
    pos.push_back(make_pair(r, c));
  }
  sort(pos.begin(), pos.end());
  
  dp[0][0] = 1;
  for (int i = 1; i < pos.size(); i++) {
    for (int j = 0; j < i; j++) {
      if (pos[j].first <= pos[i].first && pos[j].second <= pos[i].second) {
        int dr = pos[i].first - pos[j].first;
        int dc = pos[i].second - pos[j].second;
        Int coef = comb(dr + dc, dc);
        dp[i][0] = (dp[i][0] + dp[j][1] * coef) % MOD;
        dp[i][1] = (dp[i][1] + dp[j][0] * coef) % MOD;
      }
    }
  }
  
  printf("%lld\n", (dp[n + 1][1] - dp[n + 1][0] + MOD) % MOD);
  
  return 0;
}

*1:厳密には $g(r, c)$ :=( $(1, 1)$ から $(r, c)$ まで、偶数個の壁マスにマークをつけて到達する方法の個数)としたほうが適切だが、表現がややこしいため上記では簡略化して記載した。