『计数DP』CF559C：Gerald and Giant Chess

$\mathrm{Problem}$Problem

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

$\mathrm{Solution}$Solution

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

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

对于$(x_1,y_1)$(x1​,y1​)到$(x_2,y_2)$(x2​,y2​),方案数是：$C_{x_2-x_1+y_2-y_1}^{x_2-x_1}\ \ \mathrm{or}\ \ C_{x_1-x_2+y_2-y_1}^{y_2-y_1}$Cx2​−x1​+y2​−y1​x2​−x1​​  or  Cx1​−x2​+y2​−y1​y2​−y1​​

由于是坐标，起点到(x,y)的方案数：$C_{x+y-2}^{x-1}\ \ \mathrm{or}\ \ C_{x+y-2}^{y-1}$Cx+y−2x−1​  or  Cx+y−2y−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}$f[i]=Cxi​+yi​−2xi​−1​−xj​≤xi​,yj​≤yi​∑​f[j]∗Cxi​−xj​+yi​−yj​yi​−yj​​

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

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

$\mathrm{Code}$Code

#include <cstdio>
#include <iostream>
#include <algorithm>

#define int long long

using 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;
}