QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#43743 | #2834. Nonsense | xiaoyaowudi | WA | 1ms | 3820kb | C++14 | 2.1kb | 2022-08-10 16:44:46 | 2022-08-10 16:44:48 |
Judging History
answer
#include <cstdio>
#include <algorithm>
using namespace std;
constexpr int N=5010,p=998244353;
int inv[N<<1],n,x,y,q,fac[N<<1],ifac[N<<1];
int fp(int a,int b){int ans=1,off=a;while(b){if(b&1) ans=1ll*ans*off%p;off=1ll*off*off%p;b>>=1;}return ans;}
int calc(int m,int k,int a){
static int df[N<<1];
df[0]=1;
for(int i=1;i<=k;++i) df[i]=1ll*df[i-1]*(m+i)%p*inv[i]%p;
int val=fp(p+1-a,p-2),ans=0;
for(int i=0,j=1;i<=k;++i,j=1ll*j*val%p){
ans=(ans+1ll*df[k-i]*j)%p;
}
ans=(fp(val,k)-1ll*ans*fp(a,m+1))%p;
ans=1ll*val*(ans+p)%p;
return ans;
}
int main(){
inv[1]=1;
for(int i=2;i<(N<<1);++i) inv[i]=1ll*inv[p%i]*(p-p/i)%p;
fac[0]=ifac[0]=1;
for(int i=1;i<(N<<1);++i) fac[i]=1ll*fac[i-1]*i%p,ifac[i]=1ll*ifac[i-1]*inv[i]%p;
while(scanf("%d%d%d%d",&n,&x,&y,&q)!=EOF){
int k=1ll*x*fp(y,p-2)%p;
int mxa=0,mxb=0;
constexpr int Q=200010;
static int qs[Q][2];
for(int i=1;i<=q;++i){
scanf("%d%d",&qs[i][0],&qs[i][1]);
mxa=max(mxa,qs[i][0]);
mxb=max(mxb,qs[i][1]);
}
if(!x || !y){
static int nfac[N<<1],nifac[N<<1];
nfac[0]=nifac[0]=1;
for(int i=1;i<=mxa+mxb+1;++i) nfac[i]=1ll*nfac[i-1]*(n-i+1)%p,nifac[i]=1ll*nifac[i-1]*fp(n-i+1,p-2)%p;
for(int i=1;i<=q;++i){
int a=qs[i][0],b=qs[i][1];
if(a+b==b){printf("1\n");}
else{
int ans=(1ll*nfac[a+b]*nifac[a]%p*ifac[b]%p*fp(y,n-a-b)
+1ll*nfac[a+b]*nifac[b]%p*ifac[a]%p*fp(x,n-a-b))%p;
printf("%d\n",ans);
}
}
continue;
}
if(k==1){
static int df[N<<1];
df[0]=1;
for(int i=1;i<=mxa+mxb+1;++i) df[i]=1ll*df[i-1]*inv[i]%p*(n-i+2)%p;
for(int i=1;i<=q;++i){
printf("%lld\n",1ll*df[qs[i][0]+qs[i][1]+1]*fp(x,n-qs[i][0]-qs[i][1])%p);
}
continue;
}
static int f[N][N];
for(int i=0;i<=mxa;++i){
f[i][0]=calc(n-i,i,k);
}
int ik=fp(k,p-2);
for(int i=1;i<=mxb;++i){
f[0][i]=1ll*calc(n-i,i,ik)*fp(k,n-i)%p;
}
int val=fp(k-1,p-2);
for(int i=1;i<=mxa;++i) for(int j=1;j<=mxb;++j) if(i+j<=n){
f[i][j]=1ll*val*(f[i][j-1]-f[i-1][j]+p)%p;
}
for(int i=1;i<=q;++i) printf("%lld\n",1ll*f[qs[i][0]][qs[i][1]]*fp(y,n-qs[i][0]-qs[i][1])%p);
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3820kb
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: 1ms
memory: 3820kb
input:
1000000000 0 1 1 1000 1000 2 0 0 1 1 1 2 998244352 998244352 1 1 1
output:
381781645 2 1
result:
wrong answer 2nd lines differ - expected: '1', found: '2'