QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#613447#1882. Drunkardskonata2828RE 0ms0kbC++171.5kb2024-10-05 14:01:552024-10-05 14:05:34

Judging History

你现在查看的是最新测评结果

  • [2024-10-05 14:05:34]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-10-05 14:01:55]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Dangerous Syscalls

input:

2 28
1 1

output:


result: