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

发表于 | 分类于 | | + s

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;
}
------ 本文结束 ------