QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#423255 | #2834. Nonsense | DaiRuiChen007 | TL | 0ms | 0kb | C++14 | 1.2kb | 2024-05-27 21:52:44 | 2024-05-27 21:52:44 |
answer
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=5005,MAXQ=2e5+5,MOD=998244353;
ll ksm(ll a,ll b=MOD-2,ll p=MOD) {
if(b<0) b+=MOD-1;
ll ret=1;
for(;b;a=a*a%p,b>>=1) if(b&1) ret=ret*a%p;
return ret;
}
int n,q,s,t,m=0;
int a[MAXQ],b[MAXQ];
ll f[MAXN][MAXN],C[MAXN<<1];
void solve() {
m=0;
for(int i=1;i<=q;++i) scanf("%d%d",&a[i],&b[i]),m=max({m,a[i],b[i]});
if(s==t) {
C[0]=1;
for(int i=1;i<=min(2*m,n);++i) {
C[i]=C[i-1]*(n-i+1)%MOD*ksm(i)%MOD;
}
for(int i=1;i<=q;++i) printf("%lld\n",ksm(s,n-a[i]-b[i])*C[a[i]+b[i]]%MOD);
return ;
}
C[0]=1;
for(int i=1;i<=m;++i) {
C[i]=C[i-1]*(n-i+2)%MOD*ksm(i)%MOD;
}
for(int i=0;i<=m;++i) for(int j=0;j<=m;++j) f[i][j]=0;
for(int i=0;i<=m;++i) {
f[i][0]=(f[i][0]+C[i]*ksm(s,n+1-i))%MOD;
f[0][i]=(f[0][i]-C[i]*ksm(t,n+1-i))%MOD;
if(f[0][i]<0) f[0][i]+=MOD;
}
int w=ksm((s+MOD-t)%MOD);
for(int i=0;i<=m;++i) for(int j=0;j<=m;++j) {
if(i) f[i][j]=(f[i][j]+MOD-f[i-1][j])%MOD;
if(j) f[i][j]=(f[i][j]+f[i][j-1])%MOD;
f[i][j]=f[i][j]*w%MOD;
}
for(int i=1;i<=q;++i) printf("%lld\n",f[a[i]][b[i]]);
}
signed main() {
while(scanf("%d%d%d%d",&n,&s,&t,&q)) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Time Limit Exceeded
input:
3 1 2 2 1 1 1 2 100 2 3 1 1 1
output:
6 1 866021789 866021789 866021789 866021789 866021789 866021789 866021789 866021789 866021789 866021789 866021789 866021789 866021789 866021789 866021789 866021789 866021789 866021789 866021789 866021789 866021789 866021789 866021789 866021789 866021789 866021789 866021789 866021789 866021789 866021...