P3198 [HNOI2008]遥远的行星

洛谷-P3198 [HNOI2008]遥远的行星

题意

现在给定一个序列 $\{a\}$，令 $f(i,j)=\frac{a_i \times a_j}{j-i}$。对于每个 $i$，计算出所有满足 $j\leq i \times k$ 的 $f(i,j)$，（其中 $k$ 为一个小于 $0.35$ 的常量），相对误差小于 $5\%$。

Sol

我们发现所有需要计算的 $f(i,j)$ 满足 $j>i$，如果没有分母 $j-i$ 的限制，我们可以直接记录每次的和优化转移过程。但是发现这样子其实不太行。然而对于相对误差在一定范围内，那么其实我们可以考虑在每一次暴力计算精确值后，可以调用此精确值来计算其后的一部分使得误差较小。其实就是每隔一段时间后，暴力计算精确值来校正精度。

#include<bits/stdc++.h>
using namespace std;

template <typename T>
inline T read(){
	T x=0,f=1;char c=getchar();
	while(!isdigit(c)){	if(c=='-') f=-f;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+(c-48);c=getchar();}
	return x*f;
}

#define lint long long int
#define ulint unsigned lint
#define readint read<int>()
#define readlint read<lint>()
const int inf=1e9+1e7,MAXN=1e5+1e1;
const lint INF=1e18+1e9;

double a[MAXN],k,Ans;
int n,p,lp,cnt=0;

void Solve(int i){//brute
	Ans=0.0,cnt=0;
	for(int j=1;j<=p;j++) Ans+=a[i]*a[j]/(i-j);
	printf("%.6lf\n",Ans);
	return;
}

int main(void){

	cin>>n>>k;
	for(int i=1;i<=n;i++) scanf("%lf",&a[i]);
	for(int i=1;i<=n;i++){
		p=1.0*i*k,lp=1.0*(i-1)*k;
		if(i<=5000) Solve(i);
		else{
			if(cnt<100){//max{ p - lp } = 1
				++cnt,Ans*=a[i]/a[i-1];
				if(lp<p) Ans+=a[i]*a[p]/(i-p);
				printf("%.6lf\n",Ans);
			}
			else Solve(i);
		}
	}

	return 0;
}