QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#778708 | #1882. Drunkards | yjs_ | WA | 0ms | 3908kb | C++20 | 1.2kb | 2024-11-24 15:52:36 | 2024-11-24 15:52:37 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
const int mod=998244353;
const int N=5010;
int n,m,s,l,p,a[N],f[N<<1],g[N<<1];
inline int read()
{
char x=getchar();
int ans=0;
while(x<'0'||x>'9')
x=getchar();
while(x>='0'&&x<='9')
{
ans=(ans<<1)+(ans<<3)+(x^48);
x=getchar();
}
return ans;
}
int qpow(int x,int k)
{
int ans=1;
while(k)
{
if(k&1)
ans=(ll)ans*x%mod;
x=(ll)x*x%mod;
k>>=1;
}
return ans;
}
void add(int &x,int y)
{
x=(x+=y)>=mod?x-mod:x;
}
int main()
{
n=read(),p=read();
for(int i=1;i<=n;i++)
a[i]=read();
f[n]=1;
int pstop=(ll)p*qpow(100,mod-2)%mod;
int pgo=(1-pstop+mod)%mod;
for(int i=1;i<=n;i++)
{
memcpy(g,f,sizeof(g));
memset(f,0,sizeof(f));
for(int j=0;j<=2*n;++j)
{
if(!g[j])
continue;
add(f[j],(ll)g[j]*pstop%mod);
add(f[j+a[i]],(ll)g[j]*pgo%mod);
}
f[n]=1;
// cout<<"I"<<i<<endl;
// for(int j=0;j<=2*n;j++)
// {
// cout<<j<<" "<<f[j]<<endl;
// }
}
int ans=0;
for(int i=0;i<=2*n;i++)
add(ans,f[i]);
// cout<<ans<<endl;
ans=(ll)ans*qpow(2*n+1,mod-2)%mod;
printf("%d\n",ans);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3892kb
input:
2 28 1 1
output:
702764025
result:
ok 1 number(s): "702764025"
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 3908kb
input:
5 50 -1 1 -1 -1 -1
output:
952869610
result:
wrong answer 1st numbers differ - expected: '17015529', found: '952869610'