Codeforces559C.Gerald and Giant Chess

题目大意

\(h\times w(1\leq h,m\leq 10^5)\) 的棋盘，棋盘中有 \(n(1\leq n\leq 2000)\) 个不能通过的黑色格子，左上角和右下角的格子一定都是白色的。从左上角开始，每次只能向下或向右走一格，求有多少种走到右下角格子的方法。

思路

由于黑点的数量非常少，我们可以考虑根据黑点来进行计算，我们对所有黑点排序，然后逐个处理，设 \(dp[i]\) 为从起点出发，经过的第一个黑点为第 \(i\) 个黑点是的走法数量。对于第 \(i\) 个黑点 \((x_{i},y_{i})\) ，枚举所有 \(x_{j} 并且 \(y_{j}\leq y_{i}\) 的黑点 \(j\) ， 于是有

其中 \(\binom{x_{i}+y_{i}-2}{x_{i}-1}\) 为从起点在没有任何限制的情况下走到 \((x_{i},y_{i})\) 的走法数量， \(dp[j]\times \binom{x_{i}-x_{j}+y_{i}-y_{j}}{x_{i}-x_{j}}\) 为枚举了 \(j\) 为第一个经过的黑色点后，再走到第 \(i\) 个黑色点的数量。我们不妨将终点设为第 \(n+1\) 个黑色点，也对其进行转移，这样答案就为 \(dp[n+1]\) 。

代码

#include
#include
#include
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair PII;
#define all(x) x.begin(),x.end()
//#define int LL
//#define lc p*2+1
//#define rc p*2+2
#define endl '\n'
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#pragma warning(disable : 4996)
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
const double eps = 1e-8;
const LL mod = 1000000007;
const LL MOD = 998244353;
const int maxn = 200010;

struct Black {
	LL x, y;
}B[2010];
LL dp[2010];//出发后第一个经过的黑格子为i的方案数
int H, W, N;
LL fact[maxn], invfact[maxn];

bool cmp(const Black& a, const Black& b)
{
	if (a.x == b.x)
		return a.y < b.y;
	return a.x < b.x;
}

LL qpow(LL a, LL x, LL m)
{
	LL ans = 1;
	while (x)
	{
		if (x & 1)
			ans = ans * a % m;
		x >>= 1;
		a = a * a % m;
	}

	return ans % m;
}

LL inv(LL x, LL m)
{
	return qpow(x, m - 2, m);
}

void get_fact(LL n, LL m)
{
	fact[0] = fact[1] = 1;
	for (LL i = 2; i <= n; i++)
		fact[i] = fact[i - 1] * i % m;
}

void get_invfact(LL n, LL m)
{
	invfact[n] = inv(fact[n], m);
	for (LL i = n; i > 0; i--)
		invfact[i - 1] = invfact[i] * i % m;
}

LL C(LL x, LL y, LL m)
{
	return fact[x] * invfact[y] % m * invfact[x - y] % m;
}

void solve()
{
	get_fact(200005, mod), get_invfact(200005, mod);
	sort(B + 1, B + N + 1, cmp);
	B[N + 1].x = H, B[N + 1].y = W;
	for (int i = 1; i <= N + 1; i++)
	{
		LL x = B[i].x, y = B[i].y;
		dp[i] = C(x + y - 2, x - 1, mod);
		for (int j = 1; j < i; j++)
		{
			LL lx = B[j].x, ly = B[j].y;
			if (lx <= x && ly <= y)
				dp[i] = ((dp[i] - dp[j] * C(x - lx + 1 + y - ly + 1 - 2, x - lx + 1 - 1, mod) % mod) % mod + mod) % mod;
		}
	}
	cout << dp[N + 1] << endl;
}

int main()
{
	IOS;
	cin >> H >> W >> N;
	for (int i = 1; i <= N; i++)
		cin >> B[i].x >> B[i].y;
	solve();

	return 0;
}