QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#21287#2816. 过河卒二gsh#RE 3ms1988kbC++141.8kb2022-03-04 14:31:152022-05-08 02:50:26

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-08 02:50:26]
  • Judged
  • Verdict: RE
  • Time: 3ms
  • Memory: 1988kb
  • [2022-03-04 14:31:15]
  • Submitted

answer

//什么时候我才能有杜爷一半强啊/kk
#include<cstdio>
#include<algorithm>
using namespace std;
const int K=45,MOD=59393;
int n,m,k,f[K],fac[MOD],ifac[MOD];
struct point{int x,y;point(){x=y=0;}point(int xx,int yy){x=xx;y=yy;}}p[K];
int Min(int a,int b){return a<b?a:b;}
int Max(int a,int b){return a>b?a:b;}
int Add(int &a,int b){return(a+=b)>=MOD?a-=MOD:a;}
int vAdd(int a,int b){return(a+=b)>=MOD?a-=MOD:a;}
int Sub(int &a,int b){return(a-=b)<0?a+=MOD:a;}
int vSub(int a,int b){return(a-=b)<0?a+=MOD:a;}
int Mul(int a,int b){return 1ll*a*b%MOD;}
int qpow(int a,int b){
	int ret=1;
	while(b){if(b&1)ret=Mul(ret,a);a=Mul(a,a);b>>=1;}
	return ret;
}
int read(){
	char ch=getchar();int nn=0,ssss=1;
	while(ch<'0'||ch>'9'){if(ch=='-')ssss*=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){nn=nn*10+(ch-'0');ch=getchar();}
	return nn*ssss;
}
int C(int n,int m){if(n<m||n<0||m<0)return 0;return Mul(fac[n],Mul(ifac[m],ifac[n-m]));}
int lucas(int n,int m){
	if(n<m||n<0||m<0)return 0;if(n==0)return 1;
	return Mul(lucas(n/MOD,m/MOD),C(n%MOD,m%MOD));
}
int countway(point a,point b){
	int dx=b.x-a.x,dy=b.y-a.y,ret=0;
	for(int i=0;i<=Min(dx,dy);i++)Add(ret,Mul(lucas(dx+dy-i,i),C(dx+dy-2*i,dx-i)));
	return ret;
}
int main(){
	fac[0]=ifac[0]=1;
	for(int i=1;i<MOD;i++)fac[i]=Mul(fac[i-1],i);
	ifac[MOD-1]=qpow(fac[MOD-1],MOD-2);
	for(int i=MOD-2;i;i--)ifac[i]=Mul(ifac[i+1],i+1);
	n=read()+1;m=read()+1;k=read();
	for(int i=1;i<=k;i++){p[i].x=read();p[i].y=read();}
	p[++k].x=n;p[k].y=m;
	sort(p+1,p+k+1,[&](point a,point b){return a.x==b.x?a.y<b.y:a.x<b.x;});
	for(int i=1;i<=k;i++){
		f[i]=countway(point(1,1),p[i]);
		for(int j=1;j<i;j++){
			if(p[j].y>p[i].y)continue;
			Sub(f[i],Mul(f[j],countway(p[j],p[i])));
		}
	}
	printf("%d",f[k]);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 1988kb

input:

1737 2613 20
1695 2081
1449 1419
868 1636
879 2454
1400 1778
1364 2166
1343 1563
1229 2012
1308 1674
1712 2004
1392 1716
1118 1690
1693 1986
1641 2221
1454 1937
1554 1944
997 2083
1242 1503
990 1834
986 1438

output:

47388

result:

ok single line: '47388'

Test #2:

score: -100
Runtime Error

input:

37183 50656 20
19376 46381
26095 33186
22143 36608
22985 46098
37134 47561
29505 37971
33937 39976
30735 35845
18593 27027
24886 31630
31919 48391
31646 31818
32959 30489
28111 33154
19190 30567
21345 33181
27168 29608
25105 37750
27601 30901
31909 28946

output:


result: