bzoj3613: [Heoi2014]南园满地堆轻絮

被LCTcao了一早上，弃疗跟着肉老师做题贼舒服。。。

二分答案然后xjb check

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;

int n;LL Sa,Sb,Sc,Sd,mod;
LL pow_mod(LL A,int p)
{
    LL ans=1;
    while(p!=0)
    {
        if(p%2==1)ans=ans*A%mod;
        A=A*A%mod;p/=2;
    }
    return ans;
}
LL F(LL x){return ((Sa*pow_mod(x,3))%mod+(Sb*pow_mod(x,2))%mod+Sc*x%mod+Sd%mod)%mod;}

LL a[5100000];
bool check(LL p)
{
    LL last=0;
    for(int i=1;i<=n;i++)
    {
        if(a[i]>=last)last=max(a[i]-p,last);
        else
            if(a[i]+p<last)return false;
    }
    return true;
}
int main()
{
    
    scanf("%d%lld%lld%lld%lld%lld%lld",&n,&Sa,&Sb,&Sc,&Sd,&a[1],&mod);
    a[0]=0;
    for(int i=2;i<=n;i++)
        a[i]=(F(a[i-1])+F(a[i-2]))%mod;
        
    LL l=0,r=1000000000,ans;
    while(l<=r)
    {
        LL mid=(l+r)/2;
        if(check(mid)==true)
        {
            ans=mid;
            r=mid-1;
        }
        else l=mid+1;
    }
    printf("%lld
",ans);
    return 0;
}