QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#424115 | #2834. Nonsense | cqbzly | WA | 0ms | 3756kb | C++20 | 1.5kb | 2024-05-28 22:02:13 | 2024-05-28 22:02:14 |
Judging History
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'