QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#615504 | #1882. Drunkards | thomaswmy | WA | 0ms | 3932kb | C++14 | 1.1kb | 2024-10-05 19:06:04 | 2024-10-05 19:06:05 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N=5010;
const int Mod=1e9+7;
typedef long long ll;
int qpow(int x,ll y) {
int z=1;
for(;y;y>>=1) {
if(y&1) z=1ll*z*x%Mod;
x=1ll*x*x%Mod;
}
return z;
}
int n,p;
int a[N];
int f[N][N];
int main() {
scanf("%d%d",&n,&p);
p=1ll*qpow(100,Mod-2)*p%Mod;
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=0;i<=n+1;i++) f[n+1][i]=1;
for(int i=n;i>=1;i--) {
f[i][n+1]=1;
for(int j=0;j<=n;j++) {
f[i][j]=1ll*p*f[i+1][j]%Mod;
if(a[i]==1) {
f[i][j]=(f[i][j]+1ll*(Mod+1-p)*f[i+1][j+1])%Mod;
}
else {
if(j) f[i][j]=(f[i][j]+1ll*(Mod+1-p)*f[i+1][j-1])%Mod;
}
}
}
for(int i=n;i>=1;i--) printf("%d ",(Mod+1-f[1][i-1])%Mod);
printf("1 ");
for(int i=0;i<=n+1;i++) f[n+1][i]=1;
for(int i=n;i>=1;i--) {
f[i][n+1]=1;
for(int j=0;j<=n;j++) {
f[i][j]=1ll*p*f[i+1][j]%Mod;
if(a[i]==1) {
if(j) f[i][j]=(f[i][j]+1ll*(Mod+1-p)*f[i+1][j-1])%Mod;
}
else {
f[i][j]=(f[i][j]+1ll*(Mod+1-p)*f[i+1][j+1])%Mod;
}
}
}
for(int i=1;i<=n;i++) printf("%d ",(Mod+1-f[1][i-1])%Mod);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3932kb
input:
2 28 1 1
output:
0 0 1 11200001 68800001
result:
wrong answer 1st numbers differ - expected: '702764025', found: '0'