QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#424115#2834. NonsensecqbzlyWA 0ms3756kbC++201.5kb2024-05-28 22:02:132024-05-28 22:02:14

Judging History

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

  • [2024-05-28 22:02:14]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3756kb
  • [2024-05-28 22:02:13]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long 
#define fi first
#define se second
#define pb push_back
#define inf 0x3f3f3f3f3f3f3f3f
#define vi vector<ll>
using namespace std;
const int mod=998244353;
ll n,X,Y,f[5005][5005],g[5005],inv[5005],fac[5005];
int m,lim,a[200005],b[200005];
ll fpow(ll x,ll y=mod-2){
	ll z(1);
	for(;y;y>>=1){
		if(y&1)z=z*x%mod;
		x=x*x%mod; 
	}return z;
}
void init(int n){
	fac[0]=1;for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%mod;
	inv[n]=fpow(fac[n]);for(int i=n;i>=1;i--)inv[i-1]=inv[i]*i%mod;
}
int main(){
    //freopen("data.in","r",stdin);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    init(5000);
    while(cin>>n>>X>>Y>>m){
    	lim=0;
	    for(int i=1;i<=m;i++)cin>>a[i]>>b[i],lim=max(lim,max(a[i],b[i]));
	    g[0]=1;for(int i=1;i<=lim;i++)g[i]=g[i-1]*(n-i+2)%mod;
	    for(int i=1;i<=lim;i++)g[i]=g[i]*inv[i]%mod;//cout<<g[i]<<" ";
	    //cout<<"\n";
	    for(int i=0;i<=lim;i++)for(int j=0;j<=lim;j++)f[i][j]=0;
	    for(int i=1;i<=min(1ll*lim,n+1);i++)f[i][0]=fpow(X,n+1-i)*g[i]%mod;
	    for(int i=1;i<=min(1ll*lim,n+1);i++)f[0][i]=-fpow(Y,n+1-i)*g[i]%mod;
	    f[0][0]=(fpow(X,n+1)-fpow(Y,n+1))%mod;
	    ll tmp=fpow(X-Y);
	    for(int i=0;i<=lim;i++){
	    	for(int j=0;j<=lim;j++){
	    		if(i)f[i][j]=(f[i][j]-f[i-1][j])%mod;
	    		if(j)f[i][j]=(f[i][j]-f[i][j-1])%mod;
	    		f[i][j]=f[i][j]*tmp%mod;
			}
		}
		//cout<<f[0][0]<<"\n";
		for(int i=1;i<=m;i++){
			cin>>a[i]>>b[i];
			cout<<(f[a[i]][b[i]]+mod)%mod<<"\n";
		}
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3756kb

input:

3 1 2 2
1 1
1 2
100 2 3 1
1 1

output:

0
0

result:

wrong answer 1st lines differ - expected: '6', found: '0'