QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#618103#2834. NonsenseTx_LcyWA 14ms46564kbC++141.3kb2024-10-06 18:48:022024-10-06 18:48:03

Judging History

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

  • [2024-10-06 18:48:03]
  • 评测
  • 测评结果:WA
  • 用时:14ms
  • 内存:46564kb
  • [2024-10-06 18:48:02]
  • 提交

answer

//A tree without skin will surely die.
//A man without face will be alive.
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,j,k) for(int i=j;i<=k;++i)
#define per(i,j,k) for(int i=j;i>=k;--i)
int const N=5e3+10,M=2e5+10,mod=998244353;
int n,x,y,q,f[N][N],pw1[N],pw2[N],grC[M],A[M],B[M];
inline int qpow(int a,int b){int res=1;while (b){if (b&1) res*=a,res%=mod;a*=a,a%=mod,b>>=1;}return res;}
inline void solve(){
	while (cin>>n>>x>>y>>q){
		int maxn=0,maxm=0;
		rep(i,1,q) cin>>A[i]>>B[i],maxn=max(maxn,A[i]),maxm=max(maxm,B[i]);
		int invFac=1,invUp=1;
		grC[0]=1;
		rep(i,1,maxn+maxm+1){
			invFac*=qpow(i,mod-2),invFac%=mod;
			invUp*=(n+1-i+1)%mod,invUp%=mod;
			grC[i]=invUp*invFac%mod;
		}
		if (x==y){
			rep(i,1,q) cout<<qpow(x,n-A[i]-B[i])*grC[A[i]+B[i]+1]%mod<<'\n';
			return;
		}
		int inv=qpow(x+mod-y,mod-2);
		rep(i,0,maxn) pw1[i]=qpow(x,n-i+1);
		rep(i,0,maxm) pw2[i]=qpow(y,n-i+1);
		rep(i,0,maxn) rep(j,0,maxm){
			if (j) f[i][j]=f[i][j-1];
			else f[i][j]=pw1[i]*grC[i]%mod;
			if (i) f[i][j]+=mod-f[i-1][j];
			else f[i][j]+=mod-pw2[j]*grC[j]%mod;
			f[i][j]%=mod,f[i][j]*=inv,f[i][j]%=mod;
		}
		rep(i,1,q) cout<<f[A[i]][B[i]]<<'\n';
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int t=1;
	// cin>>t;
	while (t--) solve();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 9812kb

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: 14ms
memory: 46564kb

input:

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

output:

381781645
1

result:

wrong answer 3rd lines differ - expected: '1', found: ''