QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#451359 | #2834. Nonsense | grass8cow | WA | 12ms | 24324kb | C++17 | 1.3kb | 2024-06-23 09:10:29 | 2024-06-23 09:10:30 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int qpow(int a,int b){
int c=1;
for(;b;b>>=1){
if(b&1)c=1ll*a*c%mod;
a=1ll*a*a%mod;
}
return c;
}
void ad(int &x,int y){x+=y;if(x>=mod)x-=mod;}
int jc[10010],ij[10010],he[10010];
int N,x,y,q,f[5010][5010];
int A[200010],B[200100],n,m;
int main(){
jc[0]=ij[0]=1;
for(int i=1;i<=10000;i++)jc[i]=1ll*i*jc[i-1]%mod,ij[i]=qpow(jc[i],mod-2);
while(~scanf("%d%d%d%d",&N,&x,&y,&q)){
n=m=0;
for(int i=1;i<=q;i++)scanf("%d%d",&A[i],&B[i]),n=max(n,A[i]),m=max(m,B[i]);
for(int i=0,z=1;i<=n+m;i++){
if(i)z=1ll*z*(N+2-i)%mod;
he[i]=1ll*z*ij[i]%mod;
}
if(x==y){
for(int i=1;i<=q;i++)
printf("%d\n",1ll*qpow(x,N-A[i]-B[i])*he[A[i]+B[i]]%mod);
continue;
}
int I=(qpow(x-y,mod-2)+mod)%mod;
for(int i=0;i<=n;i++)for(int j=0;j<=m;j++){
f[i][j]=0;
if(j)ad(f[i][j],f[i][j-1]);
else ad(f[i][j],1ll*qpow(x,N+1-i)*he[i]%mod);
if(i)ad(f[i][j],mod-f[i-1][j]);
else ad(f[i][j],mod-1ll*qpow(y,N+1-j)*he[j]%mod);
f[i][j]=1ll*f[i][j]*I%mod;
}
for(int i=1;i<=q;i++)printf("%d\n",f[A[i]][B[i]]);
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 6084kb
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: 12ms
memory: 24324kb
input:
1000000000 0 1 1 1000 1000 2 0 0 1 1 1 2 998244352 998244352 1 1 1
output:
381781645 3 3
result:
wrong answer 2nd lines differ - expected: '1', found: '3'