QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#423521 | #2834. Nonsense | _qwqUwU | WA | 7ms | 26684kb | C++20 | 1.6kb | 2024-05-28 08:00:42 | 2024-05-28 08:00:43 |
Judging History
answer
#include<bits/stdc++.h>
#define pb push_back
#define P make_pair
#define fi first
#define se second
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
inline ll read(){
ll x=0,c=getchar();
while(c<'0'||c>'9')c=getchar();
while(c>='0' && c<='9')x=x*10 + c-'0',c=getchar();
return x;
}
int n,x,y,ma,mb,q;
const int mod=998244353;
inline void Ad(int &x,int y){x=x+y>=mod?x+y-mod:x+y;}
inline int ad(int x,int y){return x+y>=mod?x+y-mod:x+y;}
const int M=2e5+2;
const int N=5003;
int A[M],B[M];
int a[N][N],C[N],iv[N];
inline int fp(int x,int p=mod-2){
int res=1;
for(;p;p>>=1){
if(p&1)res=1ll*res*x%mod;
x=1ll*x*x%mod;
}
return res;
}
inline void solve(){
ma=mb=0;
rep(i,1,q)A[i]=read(),B[i]=read(),ma=max(ma,A[i]),mb=max(mb,B[i]);
C[0]=1;
rep(i,1,max(ma,mb))C[i]=1ll*C[i-1]*(n-i+2)%mod*iv[i]%mod;
const int ivx=fp(x),ivy=fp(y),iv=fp(ad(x,mod-y));
int px=fp(x,n+1),py=fp(y,n+1);
a[0][0]=ad(px,mod-py);
rep(i,1,ma)px=1ll*px*ivx%mod,a[i][0]=1ll*px*C[i]%mod;
rep(i,1,mb)py=1ll*py*ivy%mod,a[0][i]=mod-1ll*py*C[i]%mod;
rep(i,1,ma)rep(j,1,mb)a[i][j]=0;
rep(i,0,ma)rep(j,0,mb){
a[i][j]=1ll*a[i][j]*iv%mod;
Ad(a[i+1][j],mod-a[i][j]);
Ad(a[i][j+1],a[i][j]);
}
rep(i,1,q)printf("%d\n",a[A[i]][B[i]]);
}
int main(){
//freopen("data.in","r",stdin);
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
iv[1]=1;rep(i,2,N-1)iv[i]=1ll*iv[mod%i]*(mod-mod/i)%mod;
while(scanf("%d%d%d%d",&n,&x,&y,&q)!=EOF)solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5908kb
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: 7ms
memory: 26684kb
input:
1000000000 0 1 1 1000 1000 2 0 0 1 1 1 2 998244352 998244352 1 1 1
output:
381781645 0 0
result:
wrong answer 2nd lines differ - expected: '1', found: '0'