C++11(clang++ 3.9) 解法, 执行用时: 1347ms, 内存消耗: 158860K, 提交时间: 2019-07-06 19:58:50

#include<bits/stdc++.h>
#define db double
using namespace std;
const int N=10000000+100;
db a[N];
int n,k,q[N];
inline db slope(int u, int v)
{
	return (a[v]-a[u])/(v-u);
}
db ans;
long long A[N];
int l=1,r=1,in;
int main()
{
	scanf("%d%d",&n,&k);
	int x,y,z,m;
	scanf("%lld%d%d%d%d",&A[1],&x,&y,&z,&m);
	a[1]=db(A[1]);
	for(int i=2;i<=n;i++)
		A[i]=((x*A[i-1]%m*A[i-1]%m+y*A[i-2]%m+z)%m+m)%m-m/2;
	for(int i=1;i<=n;i++)
		a[i]=a[i-1]+db(A[i])+m/2;
	q[r++]=0;
	for (int i=k;i<=n;i++)
	{
		while (l+1<r&&slope(q[l],q[l+1])<slope(q[l+1],i))l++;
		ans=max(ans,slope(q[l],i));
		in=i-k+1;
		while (l+1<r&&slope(q[r-2],q[r-1])>slope(q[r-1], in))r--;
		q[r++]=in;
	}
	ans-=m/2;
	printf("%.8f\n",ans);
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 1396ms, 内存消耗: 158772K, 提交时间: 2019-08-08 20:47:21

#include<bits/stdc++.h>
#define o(j)for(int i=j;i<=n;i++)
using namespace std;typedef double D;const int N=1e7+100;D a[N],B;int n,k,q[N],l=1,r=1,g,x,y,z,m;long long A[N];D S(int u,int v){return(a[v]-a[u])/(v-u);}
main(){cin>>n>>k;cin>>A[1]>>x>>y>>z>>m;a[1]=D(A[1]);o(2)A[i]=((x*A[i-1]%m*A[i-1]%m+y*A[i-2]%m+z)%m+m)%m-m/2;o(1)a[i]=a[i-1]+D(A[i])+m/2;q[r++]=0;
o(k){while(l+1<r&&S(q[l],q[l+1])<S(q[l+1],i))l++;B=max(B,S(q[l],i));g=i-k+1;while(l+1<r&&S(q[r-2],q[r-1])>S(q[r-1],g))r--;q[r++]=g;}B-=m/2;printf("%.8f\n",B);}