QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#618100 | #2834. Nonsense | Tx_Lcy | TL | 1ms | 7680kb | C++14 | 1.3kb | 2024-10-06 18:45:15 | 2024-10-06 18:45:16 |
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],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) rep(j,0,maxm){
if (j) f[i][j]=f[i][j-1];
else f[i][j]=qpow(x,n-i+1)*grC[i]%mod;
if (i) f[i][j]+=mod-f[i-1][j];
else f[i][j]+=mod-qpow(y,n-j+1)*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: 7680kb
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