样例不过,求调
  • 板块AT_dp_y Grid 2
  • 楼主jrlzy
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/8/19 15:13
  • 上次更新2024/8/19 16:45:13
查看原帖
样例不过,求调
923469
jrlzy楼主2024/8/19 15:13
#include<bits/stdc++.h>
#define maxn 6005
#define maxm 400005
#define modd 1000000007
#define ll long long
using namespace std;
int n,w,h;
pair<int,int> a[maxn];
ll f[maxm],ivr[maxm],dp[maxn];
ll c (int x,int y) {return (((f[x]*ivr[x-y])%modd)*ivr[y])%modd;}
ll work (int x,int y) {return c(x+y,min(x,y));}
int mi (ll a,ll b)
{
	ll ret=1;
	while (b)
	{
		if (b&1) ret=(ret*a)%modd;
		a=(a*a)%modd,b>>=1;
	}
}
void init()
{
	f[0]=1,ivr[h+w-2]=mi(h+w-2,modd-2);
	for (int i=1;i<=h+w-2;i++) f[i]=(f[i-1]*i)%modd;
	for (int i=h+w-2;i>=1;i--) ivr[i-1]=(ivr[i]*i)%modd;
}
int main()
{
	cin>>h>>w>>n;
	for (int i=1;i<=n;i++) cin>>a[i].first>>a[i].second;
	init(); sort (a+1,a+n+1); a[n+1]={h,w};
	for (int i=1;i<=n+1;i++)
	{
		dp[i]=work(a[i].first-1,a[i].second-1);
		for (int j=1;j<i;j++)
			if (a[j].second<=a[i].second)
				dp[i]=(dp[i]-(dp[j]*work(a[i].first-a[j].first,a[i].second-a[j].second)%modd)+modd)%modd;
	}
	cout<<dp[n+1];
	return 0;
}
2024/8/19 15:13
加载中...