QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#613447 | #1882. Drunkards | konata2828 | RE | 0ms | 0kb | C++17 | 1.5kb | 2024-10-05 14:01:55 | 2024-10-05 14:05:34 |
answer
// Hydro submission #6700d65055b5e82bc01832fc@1728108113840
#include<bits/stdc++.h>
using namespace std;
namespace ax_by_c{
typedef long long ll;
const int mod=1e9+7;
const int N=5e3;
const int INV100=570000004;
int n,p,a[5005],q;
int f[5005][5005];
int ans[10005];
void main(){
scanf("%d %d",&n,&p);
p=(ll)p*INV100%mod;
q=(1-p+mod)%mod;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
f[n][n+0]=1;
for(int i=n;i>=1;i--){
for(int x=-n;x<=0;x++){
f[i-1][n+x]=(f[i-1][n+x]+(ll)f[i][n+x]*p)%mod;
}
for(int x=-n;x<=0;x++){
if(-n<=min(0,x+a[i])&&min(0,x+a[i])<=0){
f[i-1][n+min(0,x+a[i])]=(f[i-1][n+min(0,x+a[i])]+(ll)f[i][n+x]*q)%mod;
}
}
}
for(int x=-n;x<=-1;x++){
ans[N+x]=(ans[N+x]+f[0][n+x])%mod;
}
for(int x=-n+1;x<=-1;x++){
ans[N+x]=(ans[N+x]+ans[N+x-1])%mod;
}
for(int x=-n;x<=-1;x++){
printf("%d ",ans[N+x]);
}
printf("1 ");
memset(f,0,sizeof f);
f[n][0]=1;
for(int i=n;i>=1;i--){
for(int x=0;x<=n;x++){
f[i-1][x]=(f[i-1][x]+(ll)f[i][x]*p)%mod;
}
for(int x=0;x<=n;x++){
if(0<=max(0,x+a[i])&&max(0,x+a[i])<=n){
f[i-1][max(0,x+a[i])]=(f[i-1][max(0,x+a[i])]+(ll)f[i][x]*q)%mod;
}
}
}
for(int x=1;x<=n;x++){
ans[N+x]=(ans[N+x]+f[0][x])%mod;
}
for(int x=n-1;x>=1;x--){
ans[N+x]=(ans[N+x]+ans[N+x+1])%mod;
}
for(int x=1;x<=n;x++){
printf("%d ",ans[N+x]);
}
}
}
int main(){
freopen("god.in","r",stdin);
freopen("god.out","w",stdout);
ax_by_c::main();
return 0;
}
详细
Test #1:
score: 0
Dangerous Syscalls
input:
2 28 1 1