CF559C Gerald and Giant Chess

相当于 938E 的进阶版，DP。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 200005
const int p = 1e9 + 7;
struct node
{
	int x, y;
};
node a[N];
bool cmp(node a1, node a2)
{
	if(a1.x != a2.x)
	{
		return a1.x < a2.x;
	}
	return a1.y < a2.y;
}
int h, w, n, fac[N], inv[N], f[N];
int qpow(int x, int y)
{
	int ans = 1;
	while(y)
	{
		if(y & 1)
		{
			ans = (ans * x) % p;
		}
		x = (x * x) % p;
		y >>= 1;
	}
	return ans;
}
void init()
{
	fac[0] = 1;
	for(int i = 1; i < N; i++)
	{
		fac[i] = fac[i - 1] * i;
		fac[i] %= p;
	}
	inv[N - 1] = qpow(fac[N - 1], p - 2);
	for(int i = N - 2; i >= 1; i--)
	{
		inv[i] = (inv[i + 1] * (i + 1)) % p;
	}
	return;
}
int C(int n, int m)
{
	if(n < m)
	{
		return 0;
	}
	if(n == m || m == 0)
	{
		return 1;
	}
	return ((fac[n] * inv[m]) % p * inv[n - m]) % p;
}
signed main()
{
	init();
	scanf("%lld%lld%lld", &h, &w, &n);
	for(int i = 1; i <= n; i++)
	{
		scanf("%lld%lld", &a[i].x, &a[i].y);
	}
	a[n + 1].x = h;
	a[n + 1].y = w;
	sort(a + 1, a + n + 2, cmp);
	for(int i = 1; i <= n + 1; i++)
	{
		f[i] = C(a[i].x + a[i].y - 2, a[i].x - 1);
	}
	for(int i = 1; i <= n + 1; i++)
	{
		for(int j = 1; j <= i - 1; j++)
		{
			if(a[i].x < a[j].x || a[i].y < a[j].y)
			{
				continue;
			}
			f[i] -= f[j] * C(a[i].x + a[i].y - a[j].x - a[j].y, a[i].x - a[j].x);
			f[i] = (f[i] + p) % p;
		}
	}
	printf("%lld", (f[n + 1] + p) % p);
	return 0;
}