CF-559C Gerald and Giant Chess

CF-559C Gerald and Giant Chess / AtCoder DP-Y Grid 2

给定一个 $H*W$ 的棋盘，棋盘上只有 $N$ 个格子是黑色的，其他格子都是白色的。在棋盘左上角有一个卒，每一步可以向右或者向下移动一格，并且不能移动到黑色格子中。求这个卒从左上角移动到右下角，一共有多少种可能的路线。

$(1 ≤ h, w ≤ 105, 1 ≤ n ≤ 2000)$

$O(hw)$ 的暴力 DP 很好想，但是过不了。

假设没有障碍，从 $(1, 1)$ 到 $(i, j)$ 的方案数是 $C_{i+j-2}^{i-1}$（等于 $C_{i+j-2}^{j-1}$）。可以这么理解：可以用 $D, R$ 来表示一条路径，那么从 $(1, 1)$ 到 $(i, j)$ 的路径中有 $i-1$ 个 $D$ 和 $j-1$ 个 $R$。于是问题转化为从 $i+j-2$ 个位置中选 $i-1$ 个放 $D$ 的方案数。

如果有一个障碍，从正面统计方案数很困难，正难则反，考虑将总的方案数减去经过障碍的方案数。假设障碍的位置是 $(x, y)$，终点是 $(h, w)$，经过障碍的方案数就是 $C_{x+y-2}^{x-1} * C_{h-x+w-y}^{h-x}$（乘法原理）。

有多个障碍怎么办呢？联想到容斥原理，将总的方案数减去至少经过 $1$ 个障碍的，加上 $2$ 个的，减去 $3$ 个的……但这样做复杂度很高。

可以设 $dp_i$ 表示从 $(1, 1)$ 到 $(x_i, y_i)$ 且中途不经过其它障碍的方案数。令终点 $(h, w)$ 为第 $n+1$ 个障碍，求的答案就是 $dp_{n+1}$。

依然是正难则反，得出方程：$dp_i = C_{x_i+y_i-2}^{x_i-1}-\sum_{j=1}^{i-1}dp_j*C_{x_i-x_j+y_i-y_j}^{x_i-x_j}$。这样就可以巧妙地利用前面的状态不重不漏地计数了。

要写逆元。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const LL p = 1000000007;
int h, w, n;
LL dp[3005], fac[300010], inv[300010], invf[300010];
LL C(int n, int k) {
  if (n == k || k == 0) return 1;
  return fac[n] * invf[k] % p * invf[n - k] % p;
}
LL calc(int x1, int y1, int x2, int y2) { return C(x2 + y2 - x1 - y1, x2 - x1); }
struct za {
  int r, c;
  bool operator<(const za& b) {
    if (r != b.r) return r < b.r;
    return c < b.c;
  }
} a[3005];
int main() {
  ios::sync_with_stdio(false);
  inv[1] = invf[1] = fac[1] = 1;
  for (int i = 2; i <= 300000; i++) {
    inv[i] = (p - p / i) * inv[p % i] % p;
    invf[i] = invf[i - 1] * inv[i] % p;
    fac[i] = (fac[i - 1] * i) % p;
  }
  cin >> h >> w >> n;
  for (int i = 1; i <= n; i++) cin >> a[i].r >> a[i].c;
  sort(a + 1, a + 1 + n);
  a[++n] = {h, w};
  for (int i = 1; i <= n; i++) {
    dp[i] = calc(1, 1, a[i].r, a[i].c);
    for (int j = 1; j < i; j++) {
      if (a[j].r <= a[i].r && a[j].c <= a[i].c)
        dp[i] = (dp[i] - dp[j] * calc(a[j].r, a[j].c, a[i].r, a[i].c) % p + p) % p;
    }
  }
  cout << dp[n] << endl;
  return 0;
}

Orz：AT4546 题解 - GaryH

#OI #算法 #数据结构 #数学 #组合数学 #DP #容斥原理 #逆元