Codeforces 559C (DP+组合数经典模型)

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

刚开始想到本题就是求出过黑点的方案,然后用总方案减一下就好。
所以设出了$f(i)$表示前$i$个黑点中途一定走到黑点的方案,因此为了转移的方便,我们将点按$x,y$增序排序。方便起见,将$(1,1),(h,w)$加入黑点。
然后转移发现并不好转移。。然后我就设出答案的一个函数$g(i)=C^{x_i-1}_{x_i+y_i-2} - f(i)$表示前$i$个黑点中途一定不走到黑点的方案。

然后对于$f(i)$的转移就可以是$f(i)=g(j) \cdot C^{\Delta x}_{\Delta x+\Delta y}$

然后可以将两个函数合并成一个函数

$$
dp(i)=C^{x_i-1}_{x_i+y_i-2} - dp(j) \cdot C^{\Delta x}_{\Delta x+\Delta y}
$$

然后转移即可。答案为$dp(n)$

1、定义了$dp$状态或者函数,要将定义写明白,不要自己在心中知道了就行,否则会混乱
2、认为错的东西可以捡回来继续探究
3、阶乘算 $C$ 要注意 $C$ 中参数取值范围,切忌直接用 $H, W$ 的范围!

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const LL MO = 1e9 + 7;
struct data {
int x, y;
bool operator < (const data &rhs) const {
return (x == rhs.x) ? y < rhs.y : x < rhs.x;
}
}pnt[2000 + 5];
int h, w, n;
LL fac[300000 + 5], inv_fac[300000 + 5], dp[2000 + 5];
LL ksm(LL a, LL b) {
LL bs = a, ans = 1ll;
while (b) {
if (b & 1ll) ans = (ans * bs) % MO;
bs = (bs * bs) % MO;
b >>= 1ll;
}
return ans;
}
LL C(LL n, LL m) {
if (n < 0 || m < 0) return 0ll;
if (n < m) return 0ll;
LL ans = fac[n];
ans = (ans * inv_fac[m]) % MO;
ans = (ans * inv_fac[n - m]) % MO;
return ans;
}
void clean() {
ms(dp, 0);
}
int solve() {
clean();
scanf("%d%d%d", &h, &w, &n);
pnt[n + 1] = (data){1, 1}, pnt[n + 2] = (data){h, w};
for (int i = 1; i <= n; ++i) scanf("%d%d", &pnt[i].x, &pnt[i].y);
n += 2, sort(pnt + 1, pnt + 1 + n);
fac[0] = inv_fac[0] = 1ll;
for (int i = 1; i <= 300000; ++i) fac[i] = (fac[i - 1] * i) % MO, inv_fac[i] = (inv_fac[i - 1] * ksm(i, MO - 2)) % MO;
// 阶乘要处理到 2 * n, 因为下面会用到 (dx + dy)!
for (int i = 1; i <= n; ++i) {
dp[i] = C(pnt[i].x + pnt[i].y - 2ll, pnt[i].x - 1ll);
for (int j = 2; j < i; ++j) {
int dx = pnt[i].x - pnt[j].x, dy = pnt[i].y - pnt[j].y;
// dx, dy 本身已经减1,无需再减
dp[i] = (dp[i] - C(dx + dy, dx) * dp[j] % MO + MO) % MO;
}
}
cout << dp[n];
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}

------ 本文结束 ------