QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#21323#2816. 过河卒二DaBenZhongXiaSongKuaiDi#WA 7ms4032kbC++202.2kb2022-03-04 15:27:422022-05-08 02:53:03

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:53:03]
  • Judged
  • Verdict: WA
  • Time: 7ms
  • Memory: 4032kb
  • [2022-03-04 15:27:42]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define mp make_pair
typedef long long ll;
const int p=59393,maxm=(int)1e5+5;
int n,m,k,inv[maxm],cnt[21],cnt_[21]; pii seq[21];
inline void add(int x,int&a,int&b) {while(!(x%p))++b,x/=p;a=(ll)a*x%p;}
inline void del(int x,int&a,int&b) {while(!(x%p))--b,x/=p;a=(ll)a*inv[x]%p;}
inline int calc(int x,int y){
	if(!x || !y) return 1;
	int k=max(x,y),up=1,up_=0,dn=1,dn_=0,ret=0;
	for(int al=1;al<=x+y-k;al++)
		add(k+1-al,up,up_),add(al,dn,dn_);
	for(int al=1;al<=k-x;al++)
		add(2*k-x-y+1-al,up,up_),add(al,dn,dn_);
	ret=(ret+ up_>dn_ ? 0:(ll)up*inv[dn]%p);
//	printf("d %d\n",ret);
//	printf("check\n");
	while(k<x+y){

		del((k+1)-(x+y-k),up,up_),del((k+2)-(x+y-k),up,up_);
		add(k+1,up,up_);
		del(x+y-k,dn,dn_);

		del((2*k-x-y+1)-(k-x),up,up_);
		add(2*k-x-y+1,up,up_),add(2*k-x-y+2,up,up_);
		add(k-x+1,dn,dn_);

//		printf("dif=%d %d %d\n",up_>dn_ ? 0:(ll)up*inv[dn]%p,ret,k);
		ret=(ret+ (up_>dn_ ? 0:(ll)up*inv[dn]%p))%p;
//		printf("dif=%d %d %d\n",up_>dn_ ? 0:(ll)up*inv[dn]%p,ret,k);
		++k;
	}
	return ret;
}
int main(){
	inv[1]=1;
	for(int al=2;al<p;al++) inv[al]=(p-(ll)(p/al)*inv[p%al]%p)%p;
	scanf("%d%d%d",&n,&m,&k);
//	printf("c %d\n",calc(n,m));
	for(int al=1;al<=k;al++) scanf("%d%d",&seq[al].first,&seq[al].second);
	sort(seq+1,seq+k+1);
	for(int al=1;al<=k;al++){
		cnt[al]=calc(seq[al].first-1,seq[al].second-1);
		for(int be=1;be<al;be++) if(seq[be].first<=seq[al].first && seq[be].second<=seq[be].second)
			cnt[al]=(cnt[al]-(ll)calc(seq[al].first-seq[be].first,seq[al].second-seq[be].second)*cnt[be]%p+p)%p;
	}
	reverse(seq+1,seq+k+1);
	for(int al=1;al<=k;al++){
		cnt_[al]=calc(n+1-seq[al].first,m+1-seq[al].second);
		for(int be=1;be<al;be++) if(seq[be].first>=seq[al].first && seq[be].second>=seq[al].second)
			cnt_[al]=(cnt[al]-(ll)calc(seq[be].first-seq[al].first,seq[be].second-seq[al].second)*cnt_[be]%p+p)%p;
	}
	reverse(seq+1,seq+k+1);
	int ans=calc(n,m);
	for(int al=1;al<=k;al++)for(int be=1;be<=al;be++) if(seq[be].first<=seq[al].first && seq[be].second<=seq[al].second)
		ans=(ans-(ll)cnt_[al]*cnt[be]%p*calc(seq[al].first-seq[be].first,seq[al].second-seq[be].second)%p+p)%p;
	printf("%d\n",ans);
	return 0;
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 7ms
memory: 4032kb

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:

4142

result:

wrong answer 1st lines differ - expected: '47388', found: '4142'