题目链接
题目出处
菩萨蛮·南园满地堆轻絮
温庭筠
南园满地堆轻絮，愁闻一霎清明雨。雨后却斜阳，杏花零落香。
无言匀睡脸，枕上屏山掩。时节欲黄昏，无憀独倚门。
(Solution)
这个可以二分一下，再贪心的构造式子,如果满足则(r)变小,反之(l)变大很好理解的。
(Code)
#include<bits/stdc++.h>
#define int long long
#define rg register
#define file(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);
using namespace std;
int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9') f=(c=='-')?-1:1,c=getchar();
while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();
return f*x;
}
int a[5000010],b[5000010];
int n,Sa,Sb,Sc,Sd,mod,maxx;
int calc(int x){
return (((Sa*x%mod*x%mod*x%mod+Sb*x%mod*x%mod)%mod+Sc*x%mod)%mod+Sd)%mod;
}
bool check(int x){
for(int i=1;i<=n;i++)
b[i]=a[i];
for(int i=1;i<=n;i++){
if(b[i]+x<b[i-1]) return 0;
if(b[i]<b[i-1]) b[i]=b[i-1];
else b[i]=max(b[i-1],b[i]-x);
}
return 1;
}
main(){
n=read(),Sa=read(),Sb=read(),Sc=read(),Sd=read(),maxx=a[1]=read(),mod=read();
for(int i=2;i<=n;i++)
a[i]=(calc(a[i-1])+calc(a[i-2]))%mod,maxx=max(maxx,a[i]);
int l=0,r=maxx,minx=2147483647;
while(l<=r){
int mid=(l+r)>>1;
if(check(mid)) r=mid-1,minx=min(minx,mid);
else l=mid+1;
}
printf("%lld",minx);
return 0;
}