Codeforces 559C 详细题解

文章目录

- - 1. 题意
  - 2. 题解
  - - 2.1 情况0：如果不存在障碍物
    - 2.2 情况1: 如果存在一个障碍物
    - 3.3 情况2：如果存在两个障碍物
    - 3.4 情况3: 如果存在多个障碍物
  - 4. 代码实现
  - 5. 从集合角度看
  - 6. 参考

1. 题意

给定 $h\times w$ 大小的二维数组，再给定 $n$ 个障碍

物。我们从左上角出发，每次只能向右或者向下走

动，问有多少种方法从左上到右下？

cf559c

2. 题解

动态规划+组合计数+容斥原理+乘法逆元

我们一步步慢慢分析

2.1 情况0：如果不存在障碍物

首先我们分析，如果没有障碍物，

从 $(0, 0)$ 到 $(x, y)$ 一共有多少种走法呢？没错应该是

$\choose x}$ 种。为什么呢？我们一共要走

$x + y$ 步， $x$ 步向下， $y$ 步向右，因此也就是 $x + y$

步中选择 $x$ 步向下，或者 $y$ 步向下，也就是

$\choose x}={x+y \choose y}$

2.2 情况1: 如果存在一个障碍物

如果在 $(0, 0)$ 和 $(x, y)$ 之间存在一个障碍物

$x_0,y_0)$ , 我们可以直接用总数减去通过该障碍物的

路径数目。经过障碍物到达右下的路径数可以通过

乘法计数来求得

${x_0+y_0 \choose x_0}{x+y-x_0-y_0 \choose x-x_0}$

因此最终的路径数目为
$\choose x}-\\{x_0+y_0 \choose x_0}{x+y-x_0-y_0 \choose x-x_0}$

3.3 情况2：如果存在两个障碍物

假设这两个障碍物位置为

$B_0(x_0, y_0), B_1(x_1, y_1)$

我们需要分情况进行讨论，这两个障碍物是否

独立。所谓独立就是说，在经过 $B_0$ 去往右下角终点

的路径上是否会出现点 $B_1$ ; 如果出现了，那么在计

数的时候就会出现重复，需要去除重复的路径数。

我们容易得到，如果两者之间只要满足

$x_0-x_1)(y_0-y_1) < 0$ ，它们两点之间就独立。

对于独立的点，我们逐个减去经过它到达终点

的方案数就可以了。

$\choose x} -\\\sum_{i=0}^1{x_i+y_i \choose x_i} { x-x_i+y-y_i \choose x-x_i}$

而对于两点不独立存在重复的情况，我们要试

着让他们独立。

假设 $B_1在B_0$ 的右下，也就是 $x_0 <= x_1 \land y_0 <= y_1$ 。

我们在计算经过 $B_0$ 到达右下角的路径中必然包

含了同时经过 $B_0B_1$ 到达右下角的路径，因此我们

只需要计算经过 $B_1$ 而经过 $B_0$ 到达右下角的路径数

目。也就是到达 $B_1$ 的路径上不能有其他障碍物，而

从左上角不经过障碍物到 $B_1$ 的方案数实际上就是求

情况1。

我们定义 $d p [i] [j]$ 为不经过障碍物从 $(0, 0)$ 到达

$(i, j)$ 的可能路径数。最终的路径数为：

$\choose x}-\\\sum_{i=0}^1dp[x_i][y_i]{x+y-x_i -y_i \choose x-x_i}$

3.4 情况3: 如果存在多个障碍物

多个障碍物独立的情况仍然是直接减就可以了
$\choose x} -\\\sum_{i=0}^k{x_i+y_i \choose x_i} { x-x_i+y-y_i \choose x-x_i}$
如果这 $k$ 个点都不独立，我们需要从左

上的点开始算，因为它会包含经过后面障碍的路

径。依次将它们独立，也就是依次求出 $dp[x_i][y_i]$

再像处理情况2那样处理最终的路径数

$\choose x}-\\\sum_{i=0}^kdp[x_i][y_i]{x+y-x_i -y_i \choose x-x_i}$

4. 代码实现

我们将右下角坐标也放入障碍物数组，再

将障碍物按左上右下的顺序进行排序；依次求

$dp[x_i][y_i]$ 即可；组合数较大需要取模，预处理乘

法逆元就可以了, 可以用费马小+快速幂或者是扩展

欧几里得求出最大的阶乘逆元，再线性递推求出其

他阶乘的逆元。

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>using ll = long long;static constexpr int MAXN = 200005;ll fac[MAXN + 1];
ll ifac[MAXN + 1];
ll MOD = 1e9 + 7;ll exgcd(ll a, ll b, ll &x, ll &y) {if (0 == b) {x = 1;y = 0;return a;}ll d = exgcd( b, a % b, y, x);y -= (a / b) * x;return d;
}
ll fpow(ll base, ll cnt) {ll ans = 1;ll tmp = base;while (cnt) {if (cnt & 1) ans = ans * tmp % MOD;tmp = tmp * tmp % MOD;cnt >>= 1;}return ans;
}void init () {fac[0] = ifac[0] = 1;fac[1] = 1;ifac[1] = 1;for (int i = 2; i <= MAXN; i++) {fac[i] = fac[i - 1] * i % MOD; }//ll y;//exgcd( fac[MAXN], MOD, ifac[MAXN], y);ifac[MAXN] = fpow(fac[MAXN], MOD - 2);for (int i = MAXN - 1; i > 1; i--) {ifac[i] = ifac[i + 1] * (i + 1) % MOD;}}
ll Comb(int n, int k) {if (n == k || k == 0) {return 1;}return fac[n] * ifac[k] % MOD * ifac[n - k] % MOD;
}
int main()
{init();int h;int w;int n;std::cin >> h >> w >> n;std::vector<std::pair<int, int> > b;for (int i = 0;i < n;i++) {int x;int y;std::cin >> x >> y;b.push_back(std::make_pair<>(x, y));}std::sort(b.begin(), b.end(),[](const std::pair<int,int> &f, const std::pair<int,int> &s){return f.first == s.first ? f.second < s.second : f.first < s.first;});b.push_back(std::make_pair( h, w));std::vector<ll> dp( n + 1, 0);for (int i = 0;i < n + 1; ++i) {int r = b[i].first;int c = b[i].second;ll res = Comb(r + c - 2, r - 1);for (int j = 0;j < i;++j) {int rr = b[j].first;int cc = b[j].second;if (rr <= r && cc <= c) {res = res + MOD -  (dp[j] * Comb(r + c - rr - cc, r - rr) % MOD) ;res = res % MOD ;}}dp[i] = res;}std::cout << dp[n] << std::endl;return 0;
}