bzoj

洛谷

这题意是不是不太清楚

真正题意:求$$f_i=\sum_{j=1}^{\lfloor iA \rfloor} \frac{M_iM_j}{i-j}$$

似乎只能\(O(n*\lfloor n*A \rfloor)\)求

但是,注意只要结果的相对误差不超过 5% 即可

于是对于较大的\(i\)来说,\(f_i\)可以近似的看为\(M_i*\frac{\sum_{j=1}^{\lfloor i*A \rfloor} M_j}{i-\frac{\lfloor i*A \rfloor}{2}}\)

因为\(A\)是一个不超过0.35的实数,并且\(i\)较大时\(i-j\)也会比较大,所以近似一下可以接受

至于为什么,emmm你猜

#include<bits/stdc++.h>

#define LL long long

#define il inline

#define re register

#define inf 2099999999

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)<(b)?(a):(b))

#define db double

#define eps (1e-5)

using namespace std;

const int N=100000+10;

il LL rd()

{

    re LL x=0,w=1;re char ch=0;

    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}

    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}

    return x*w;

}

int n,nn;

db a,m[N],ans;

int main()

{

  n=rd();scanf("%lf",&a);

  for(int i=1;i<=n;i++) scanf("%lf",&m[i]);

  nn=min(3000,n);

  for(int i=1;i<=nn;i++)

    {

      int mm=(int)(i*a+eps);

      ans=0;

      for(int j=1;j<=mm;j++) ans+=m[j]/(db)(i-j);

      ans*=m[i];

      printf("%.8lf\n",ans);

    }

  db tm=0;

  for(int i=nn+1,la=1;i<=n;i++)

    {

      int mm=(int)(i*a+eps);

      while(la<=mm) tm+=m[la++];

      ans=m[i]*tm/((db)i-(db)mm/2);

      printf("%.8lf\n",ans);

    }

  return 0;

}