QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#877384 | #1882. Drunkards | zxcen | WA | 1ms | 3712kb | C++14 | 873b | 2025-01-31 21:46:52 | 2025-01-31 21:46:52 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=5e3;
const ll mod=998244353;
int n;
ll p;
int a[N+10];
ll f[N*2+10];
inline ll qpow(ll x,ll y){
ll res=1;
while(y){
if(y&1){
res=res*x%mod;
}
x=x*x%mod;
y>>=1;
}
return res;
}
int main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n>>p;
p=p*qpow(100,mod-2)%mod;
for(int i=1;i<=n;++i){
cin>>a[i];
}
f[n]=1;
for(int i=n;i;--i){
if(~a[i]){
for(int j=n+n-i+1;j>=n-(n-i)+1;--j){
f[j]=(f[j]*p+f[j-1]*(1+mod-p))%mod;
}
}
else{
for(int j=n-(n-i)-1;j<=n+n-i-1;++j){
f[j]=(f[j]*p+f[j+1]*(1+mod-p))%mod;
}
}
f[n]=1;
}
ll ans=0;
for(int i=0;i<=n*2;++i){
ans=(ans+f[i])%mod;
}
cout<<ans*qpow(n*2+1,mod-2)%mod;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3712kb
input:
2 28 1 1
output:
702764025
result:
ok 1 number(s): "702764025"
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 3584kb
input:
5 50 -1 1 -1 -1 -1
output:
283592146
result:
wrong answer 1st numbers differ - expected: '17015529', found: '283592146'