QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#618103 | #2834. Nonsense | Tx_Lcy | WA | 14ms | 46564kb | C++14 | 1.3kb | 2024-10-06 18:48:02 | 2024-10-06 18:48:03 |
Judging History
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: ''