QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#423521#2834. Nonsense_qwqUwUWA 7ms26684kbC++201.6kb2024-05-28 08:00:422024-05-28 08:00:43

Judging History

你现在查看的是最新测评结果

  • [2024-05-28 08:00:43]
  • 评测
  • 测评结果:WA
  • 用时:7ms
  • 内存:26684kb
  • [2024-05-28 08:00:42]
  • 提交

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();
}

详细

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'