题目描述
https://codeforces.com/problemset/problem/559/C
简要题意：给定一个 $n\times m$ 的棋盘和 $k$ 个黑色的格子，求从左上角到右下角且不经过任何黑色格子的方案数，只能向右或者向下走
$n,m\le 10^5,k\le 2000$
Solution
我们考虑容斥 $dp$，令 $f_i$ 表示从左上角到第 $i$ 个黑色格子且中间不经过任何其它黑色格子的方案数
我们考虑如何从 $f_j$ 转移到 $f_i$，注意到任何一个不合法路径的存在第一个经过的黑色格子，我们可以按照第一个经过的黑色格子来区分所有不合法路径，那么我们枚举第一个黑色格子，容易得到 $f_i=\binom{x_i-1+y_i-1}{x_i-1}-\sum f_j\binom{x_i-x_j+y_i-y_j}{x_i-x_j}$
时间复杂度 $O(n+k^2)$
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
41
42
43
44
45
46
47
| #include <iostream>
#include <algorithm>
#define maxn 200010
#define maxm 2010
#define ll long long
using namespace std;
const int p = 1000000007;
ll pow_mod(ll x, ll n) {
ll s = 1;
for (; n; n >>= 1, x = x * x % p)
if (n & 1) s = s * x % p;
return s;
}
ll fac[maxn], inv[maxn];
void init_C(int n) {
fac[0] = 1; for (int i = 1; i <= n; ++i) fac[i] = fac[i - 1] * i % p;
inv[n] = pow_mod(fac[n], p - 2); for (int i = n - 1; ~i; --i) inv[i] = inv[i + 1] * (i + 1) % p;
}
ll C(int n, int m) { return n < m ? 0 : fac[n] * inv[m] % p * inv[n - m] % p; }
int n, m, k;
pair<int, int> a[maxn];
int f[maxn];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> m >> k; init_C(n + m);
for (int i = 1; i <= k; ++i) cin >> a[i].first >> a[i].second;
a[++k] = make_pair(n, m); sort(a + 1, a + k + 1);
for (int i = 1; i <= k; ++i) {
f[i] = C(a[i].first - 1 + a[i].second - 1, a[i].first - 1);
for (int j = 1; j < i; ++j) {
if (a[j].second > a[i].second) continue;
f[i] = (f[i] -
C(a[i].first - a[j].first + a[i].second - a[j].second, a[i].first - a[j].first) *
f[j]) % p;
}
} cout << (f[k] + p) % p << "\n";
return 0;
}
|