萌新求助,样例过了为什么WA
查看原帖
萌新求助,样例过了为什么WA
390770
D2T1xubiaoshi楼主2022/6/2 20:34

dpi=Cai.x+ai.y2ai.x1j=1i1,aj.yai.ydpj×Cai.xaj.x+ai.yaj.yai.xaj.x\large dp_i=C_{a_i.x+a_i.y-2}^{a_i.x-1}-\sum\limits_{j=1}^{i-1,a_j.y\leq a_i.y}dp_j\times C_{a_i.x-a_j.x+a_i.y-a_j.y}^{a_i.x-a_j.x}

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;

const int N = 2e3, M = 1e5, P = 1e9 + 7;
ll dp[N+10], A[M+10], invA[M+10];
pair<int, int> a[N+10];
int n, m, k;

ll qp(ll a, ll b){
	ll ans = 1; while(b){
		if(b & 1) ans = ans * a % P;
		a = a * a % P; b >>= 1;
	} return ans;
}
ll C(int n, int m){ return A[n] * invA[m] % P * invA[n-m] % P; }

int main(){
	A[0] = 1; for(int i = 1; i <= M+1; ++ i) A[i] = A[i-1] * (ll)i % P;
	invA[M+1] = qp(A[M+1], P-2);
	for(int i = M; i >= 0; -- i) invA[i] = invA[i+1] * (i+1) % P;
	scanf("%d%d%d", &n, &m, &k);
	for(int i = 1; i <= k; ++ i) scanf("%d%d", &a[i].x, &a[i].y);
	sort(a + 1, a + k + 1); a[k+1] = make_pair(n, m);
	for(int i = 1; i <= k + 1; ++ i){
		dp[i] = C(a[i].x + a[i].y - 2, a[i].x - 1);
		for(int j = 1; j < i; ++ j) if(a[i].y >= a[j].y)
			dp[i] = (dp[i] - dp[j] * C(a[i].x-a[j].x+a[i].y-a[j].y, a[i].x-a[j].x) % P + P) % P;
	}
	printf("%lld\n", dp[k+1]);
	return 0;
}
2022/6/2 20:34
加载中...