组合数求助,样例输出16
查看原帖
组合数求助,样例输出16
716260
SegmentTree_楼主2024/5/5 14:10
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e3+5, M = 1e5;
const ll mod = 1e9+7;
struct black{
	int x, y;
}a[N];
int h, w, n;
bool cmp(black a, black b){
	if (a.x == b.x) return a.y < b.y;
	return a.x < b.x;
}
ll f[N];
ll fac[M + 5];
ll finv[M + 5];
ll qpow(ll a, ll b, ll m){
	ll res = 1;
	while (b){
		if (b & 1) res = res * a % m;
		a = a * a % m;
		b >>= 1;
	}
	return res % m;
}
ll C(ll n, ll m){
	if (n < m) return 0;
	return (fac[n] * finv[m] % mod) * finv[n - m] % mod;
}
void init(){
	fac[0] = finv[0] = 1;
	for (int i = 1;i <= 100000;i++) fac[i] = fac[i - 1] * i % mod;
	finv[100000] = qpow(fac[100000], mod - 2, mod);
	for (int i = 100000 - 1;i >= 1;i--) finv[i] = finv[i + 1] * (ll)(i + 1) % mod;
}
int main(){
	//ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	init();
	cin >> h >> w >> n;
	for (int i = 1;i <= n;i++){
		cin >> a[i].x >> a[i].y;
	}
	sort(a + 1, a + 1 + n, cmp);
	a[n + 1].x = h, a[n + 1].y = w;
	for (int i = 1;i <= n + 1;i++){
		f[i] = C(a[i].x + a[i].y + 2, a[i].x - 1) % mod;
		for (int j = 1;j < i;j++){
			if (i == j || (a[i].x < a[j].x || a[i].y < a[j].y)) continue;
			ll tmp = f[j] * C(a[i].x - a[j].x + a[i].y - a[j].y, a[i].x - a[j].x) % mod;
			f[i] = (f[i] - tmp + mod) % mod;
		} 
	}
	cout << (f[n + 1] + mod) % mod;
	return 0;
}
2024/5/5 14:10
加载中...