【二分+贪心】BZOJ3613 [Heoi2014]南园满地堆轻絮

题面在这里

​

题解见tag

​

示例程序：

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;

const int maxn=5000005;
int n,Sa,Sb,Sc,Sd,MOD,a[maxn];
inline ll F(ll x){
	return Sa*x%MOD*x%MOD*x%MOD+Sb*x%MOD*x%MOD+Sc*x%MOD+Sd;
}
bool check(int x){
	int M=1;
	for (int i=1;i<=n;i++)
	 if (a[i]>=M) M=max(M,a[i]-x);
	 else{
	 	if (a[i]+x<M) return 0;
	 }
	return 1;
}
int main(){
	scanf("%d%d%d%d%d%d%d",&n,&Sa,&Sb,&Sc,&Sd,&a[1],&MOD);
	for (int i=2;i<=n;i++) a[i]=(F(a[i-1])+F(a[i-2]))%MOD;
	int L=0,R=MOD,ans=R;
	while (L<=R){
		int mid=L+R>>1;
		if (check(mid)) ans=mid,R=mid-1;else L=mid+1;
	}
	printf("%d",ans);
	return 0;
}