萌新救助 本地样例能过 交到cf上过不了样例 是有什么语法没有注意到吗
查看原帖
萌新救助 本地样例能过 交到cf上过不了样例 是有什么语法没有注意到吗
224111
zysqh楼主2020/7/4 20:46
#include <cstdio>
#include <iostream>
#include <algorithm>
#define mod 1000000007
#define S 100005
#define ll long long
using namespace std;
ll jie[S],invjie[S];
int calc(ll n,ll m){
	return jie[n]*invjie[m]%mod*invjie[n-m]%mod;
}
ll h,w,n;
ll f[S];
ll x,y;
void ex_gcd(ll a,ll b){
	if(!b){
         x=1;y=0;return;
	}
	ex_gcd(b,a%b);
	ll z=x;x=y;y=z-y*(a/b);
}
struct nnn{
	ll r,c;
}e[S];
bool cmp(nnn &a,nnn &b){
	if(a.r==b.r)return a.c<b.c;
	return a.r<b.r;
}
int main(){
	scanf("%lld%lld%lld",&h,&w,&n);
	jie[0]=1;
	invjie[0]=1;
	for(int i=1;i<=h+w;++i){
		jie[i]=jie[i-1]*i%mod;
		ex_gcd(mod,jie[i]);
		while(y<0)y+=mod;
		invjie[i]=y%mod;
	}
	e[n+1].r=h;e[n+1].c=w;
	for(int i=1;i<=n;++i){
		scanf("%lld%lld",&e[i].r,&e[i].c);
	}
	sort(e+1,e+n+2,cmp);
	for(int i=1;i<=n+1;++i){
		for(int j=1;j<i;++j){
			f[i]+=f[j]*calc(e[i].r+e[i].c-e[j].r-e[j].c,e[i].r-e[j].r)%mod;
		}
		f[i]=calc(e[i].r+e[i].c-2,e[i].r-1)-f[i];
		while(f[i]<0)f[i]+=mod;
		f[i]%=mod;
	}
	printf("%lld\n",(f[n+1]+mod)%mod);
}
2020/7/4 20:46
加载中...