QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#618101 | #2834. Nonsense | Tx_Lcy | TL | 1ms | 9656kb | C++14 | 1.4kb | 2024-10-06 18:46:45 | 2024-10-06 18:46:45 |
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){
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;
}
详细
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