QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#43743#2834. NonsensexiaoyaowudiWA 1ms3820kbC++142.1kb2022-08-10 16:44:462022-08-10 16:44:48

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-08-10 16:44:48]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3820kb
  • [2022-08-10 16:44:46]
  • 提交

answer

#include <cstdio>
#include <algorithm>
using namespace std;
constexpr int N=5010,p=998244353;
int inv[N<<1],n,x,y,q,fac[N<<1],ifac[N<<1];
int fp(int a,int b){int ans=1,off=a;while(b){if(b&1) ans=1ll*ans*off%p;off=1ll*off*off%p;b>>=1;}return ans;}
int calc(int m,int k,int a){
	static int df[N<<1];
	df[0]=1;
	for(int i=1;i<=k;++i) df[i]=1ll*df[i-1]*(m+i)%p*inv[i]%p;
	int val=fp(p+1-a,p-2),ans=0;
	for(int i=0,j=1;i<=k;++i,j=1ll*j*val%p){
		ans=(ans+1ll*df[k-i]*j)%p;
	}
	ans=(fp(val,k)-1ll*ans*fp(a,m+1))%p;
	ans=1ll*val*(ans+p)%p;
	return ans;
}
int main(){
	inv[1]=1;
	for(int i=2;i<(N<<1);++i) inv[i]=1ll*inv[p%i]*(p-p/i)%p;
	fac[0]=ifac[0]=1;
	for(int i=1;i<(N<<1);++i) fac[i]=1ll*fac[i-1]*i%p,ifac[i]=1ll*ifac[i-1]*inv[i]%p;
	while(scanf("%d%d%d%d",&n,&x,&y,&q)!=EOF){
		int k=1ll*x*fp(y,p-2)%p;
		int mxa=0,mxb=0;
		constexpr int Q=200010;
		static int qs[Q][2];
		for(int i=1;i<=q;++i){
			scanf("%d%d",&qs[i][0],&qs[i][1]);
			mxa=max(mxa,qs[i][0]);
			mxb=max(mxb,qs[i][1]);
		}
		if(!x || !y){
			static int nfac[N<<1],nifac[N<<1];
			nfac[0]=nifac[0]=1;
			for(int i=1;i<=mxa+mxb+1;++i) nfac[i]=1ll*nfac[i-1]*(n-i+1)%p,nifac[i]=1ll*nifac[i-1]*fp(n-i+1,p-2)%p;
			for(int i=1;i<=q;++i){
				int a=qs[i][0],b=qs[i][1];
				if(a+b==b){printf("1\n");}
				else{
					int ans=(1ll*nfac[a+b]*nifac[a]%p*ifac[b]%p*fp(y,n-a-b)
							+1ll*nfac[a+b]*nifac[b]%p*ifac[a]%p*fp(x,n-a-b))%p;
					printf("%d\n",ans);
				}
			}
			continue;
		}
		if(k==1){
			static int df[N<<1];
			df[0]=1;
			for(int i=1;i<=mxa+mxb+1;++i) df[i]=1ll*df[i-1]*inv[i]%p*(n-i+2)%p;
			for(int i=1;i<=q;++i){
				printf("%lld\n",1ll*df[qs[i][0]+qs[i][1]+1]*fp(x,n-qs[i][0]-qs[i][1])%p);
			}
			continue;
		}
		static int f[N][N];
		for(int i=0;i<=mxa;++i){
			f[i][0]=calc(n-i,i,k);
		}
		int ik=fp(k,p-2);
		for(int i=1;i<=mxb;++i){
			f[0][i]=1ll*calc(n-i,i,ik)*fp(k,n-i)%p;
		}
		int val=fp(k-1,p-2);
		for(int i=1;i<=mxa;++i) for(int j=1;j<=mxb;++j) if(i+j<=n){
			f[i][j]=1ll*val*(f[i][j-1]-f[i-1][j]+p)%p;
		}
		for(int i=1;i<=q;++i) printf("%lld\n",1ll*f[qs[i][0]][qs[i][1]]*fp(y,n-qs[i][0]-qs[i][1])%p);
	}
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3820kb

input:

3 1 2 2
1 1
1 2
100 2 3 1
1 1

output:

6
1
866021789

result:

ok 3 lines

Test #2:

score: -100
Wrong Answer
time: 1ms
memory: 3820kb

input:

1000000000 0 1 1
1000 1000
2 0 0 1
1 1
2 998244352 998244352 1
1 1

output:

381781645
2
1

result:

wrong answer 2nd lines differ - expected: '1', found: '2'