题目链接，首先理解题意
有一条数轴，\([1,n]\)每个点上都有一个行星，每个行星\(i\)都有质量\(M_i\)，同时有一个很小的实数常量\(A\)；
当\(i,j\)两个行星有着\(i\leq Aj\)的关系时，\(i\)对\(j\)有着大小为\(\frac{M_i M_j}{j-i}\)的作用力，求每个星球受到的作用力大小
首先，按照题意模拟的复杂度是\(O(An^2)\)的，肯定会超时，考虑观察题面题解，发现\(A\)很小，可以瞎搞一搞
题目让我们对于每一个\(j\)求这个东西：$$\text{Ans}_j=\sum^{\lfloor Aj\rfloor}_{k=1}\frac{M_j M_k}{j-k}$$
然后发现\(\lfloor Aj\rfloor\)在\(j\)很大时依然很小，小到\(5\%\)的误差无所畏惧，所以可以瞎搞得到：$$\text{Ans}_j\approx\sum^{\lfloor Aj\rfloor}_{k=1}\frac{M_j M_k}{j-\frac{1}{2}\times\lfloor Aj\rfloor}$$
前缀和优化即可得到：设$\text{Sum}_i=\sum^{i}_{k=1}M_k$，有：$$\text{Ans}_j\approx\frac{\text{Sum}_{\lfloor Aj\rfloor}M_j}{j-\frac{1}{2}\times\lfloor Aj\rfloor}$$时间复杂度$O(n)$
代码
/*
DOCUMENT NAME "20181128-bnds1011.cpp"
CREATION DATE 2018-11-28
SIGNATURE CODE_20181128_BNDS1011
COMMENT [HNOI2008]遥远的行星
*/
#include <cstdlib>
#include <iostream>
#include <cstdio>
#include <cctype>
#include <cmath>
using namespace std;
template<typename IntType>
void read(IntType& val) {
val = 0;
int c;
bool inv = false;
while (!isdigit(c = getchar()))
if (c == '-')
inv = true;
do {
val = (val << 1) + (val << 3) + c - '0';
} while (isdigit(c = getchar()));
if (inv)
val = -val;
}
typedef long long ll;
const int MaxN = 1e5 + 10;
int n;
double a;
int m[MaxN];
ll sum[MaxN];
int main(int argc, char* argv[]) {
read(n);
scanf("%lf", &a);
for (int i = 1; i <= n; i++) {
read(m[i]);
sum[i] = sum[i - 1] + m[i];
}
for (int i = 1; i <= n; i++) {
int fl = i * a + 1e-7;
if (i <= 1000) {
double ans = 0;
for (int j = 1; j <= fl; j++)
ans += (double)m[j] * m[i] / (i - j);
printf("%lf\n", ans);
} else
printf("%lf\n", (double)sum[fl] * m[i] / (i - .5*fl));
}
return 0;
}
