『计数DP』CF559C：Gerald and Giant Chess

$\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{b}\mathrm{l}\mathrm{e}\mathrm{m}$

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

$\mathrm{S}\mathrm{o}\mathrm{l}\mathrm{u}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}$

我们设我们将每一个黑点坐标排序。

我们设$f[i]$表示到第$i$个坐标，且中间没有经过人格其余黑点的方案数。

对于$(x_1,y_1)$到$(x_2,y_2)$,方案数是：$$C_{x_2?x_1+y_2?y_1}^{x_2?x_1}\mathrm{o}\mathrm{r}{C}_{x_1?x_2+y_2?y_1}^{y_2?y_1}$$

由于是坐标，起点到(x,y)的方案数：$$C_{x+y?2}^{x?1}\mathrm{o}\mathrm{r}{C}_{x+y?2}^{y?1}$$

这些结论很显然。

我们就可以很容易得到状态转移方程：$$f[i]=C_{x_i+y_i?2}^{x_i?1}?\sum _{x_j\le x_i,y_j\le y_i}f[j]?C_{x_i?x_j+y_i?y_j}^{y_i?y_j}$$

考虑如何做到不重不漏，显然如果当前为第一个黑点，那么一定是减去前面有可能经过的黑点的；且前面的每一个黑点都是枚举到的，因此保证了不漏。

前面的每一个决策，都保证可第一次到达的黑点不同，因此这是不漏。

$\mathrm{C}\mathrm{o}\mathrm{d}\mathrm{e}$

#include <cstdio>
#include <iostream>
#include <algorithm>#define int long longusing namespace std;
const int N = 3000;
const int V = 300000;
const int P = 1e9 + 7;int w, h, n;
int jc[V], f[N];
struct node {
    int x, y;
} a[N];int read(void)
{
    int s = 0, w = 0; char c = getchar();while (c < '0' or c > '9') w |= c == '-', c = getchar();while (c >= '0' and c <= '9') s = s*10+c-48, c = getchar();return w ? -s : s;
}int power(int a,int b)
{
    int res = 1;while (b) {
    if (b & 1) res = res * a % P;a = a * a % P, b >>= 1;}return res;
}int C(int n,int m) {
    int ret =  jc[n] * power(1LL * jc[n-m] * jc[m] % P, P-2) % P;return ret;
}bool cmp (node p1,node p2) {
    if (p1.x == p2.x) return p1.y < p2.y;else return p1.x < p2.x;
}signed main(void)
{
    freopen("chess.in","r",stdin);freopen("chess.out","w",stdout);w = read(), h = read(), n = read();for (int i=1;i<=n;++i)a[i].x = read(), a[i].y = read();jc[0] = 1;for (int i=1;i<=2e5;++i) jc[i] = jc[i-1] * i % P;sort(a+1,a+n+1,cmp);a[++n] = node{
    w,h};for (int i=1;i<=n;++i){
    f[i] = C(a[i].x+a[i].y-2,a[i].x-1);for (int j=0;j<i;++j)    {
    if (a[j].x > a[i].x or a[j].y > a[i].y) continue;f[i] -= 1LL * f[j] * C(a[i].x+a[i].y-a[j].x-a[j].y,a[i].x-a[j].x);f[i] %= P;}         }printf("%lld\n", (f[n] + P) % P);return 0;
}