QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#21287 | #2816. 过河卒二 | gsh# | RE | 3ms | 1988kb | C++14 | 1.8kb | 2022-03-04 14:31:15 | 2022-05-08 02:50:26 |
Judging History
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]);
}
詳細信息
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