定义一个常数\(T\),在\(100\)左右
\(x=\lfloor a*i\rfloor\)
当\(x≤T\)时,暴力统计。
当\(x>T\)时,把\([1,x]\)分成\(T\)个长度尽可能平均的小区间(小区间过大会使误差变大)。
每一个小区间\([x,y]\)的贡献的近似值就是\((M_i*\sum_{j=x}^yM_j)/(i-\frac{x+y}{2})\)(取中点作为分母)
由于\(0.01<a≤0.35\)得到,这个近似值与准确值的相对误差不超过5%
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define Debug(x) cout<<#x<<"="<<x<<endl
using namespace std;
typedef long long LL;
const int INF=1e9+7;
inline LL read(){
register LL x=0,f=1;register char c=getchar();
while(c<48||c>57){if(c=='-')f=-1;c=getchar();}
while(c>=48&&c<=57)x=(x<<3)+(x<<1)+(c&15),c=getchar();
return f*x;
}
const int MAXN=1e5+5;
int a[MAXN],sum[MAXN];
int n,T;
double P;
int main(){
n=read();
scanf("%lf",&P);T=pow(n,0.4);
for(int i=1;i<=n;i++){
a[i]=read();
sum[i]=sum[i-1]+a[i];
}
for(int i=1;i<=n;i++){
int r=i*P,j;
double ans=0;
for(j=1;j+T<=r;j+=T)
ans+=(double)a[i]*(sum[j+T-1]-sum[j-1])/(i-(double)(2*j+T-1)/2);
for(;j<=r;j++)
ans+=(double)a[i]*a[j]/(i-j);
printf("%.6lf\n",ans);
}
}