QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#618101#2834. NonsenseTx_LcyTL 1ms9656kbC++141.4kb2024-10-06 18:46:452024-10-06 18:46:45

Judging History

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

  • [2024-10-06 18:46:45]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:9656kb
  • [2024-10-06 18:46:45]
  • 提交

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){
			while (q--){
				int a,b;cin>>a>>b;
				cout<<qpow(x,n-a-b)*grC[a+b+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: 9656kb

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
Time Limit Exceeded

input:

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

output:


result: