分析

作为一名OIer，当看到最大值最小时
一定可以想到二分答案
所以可以顺着这个思路往下
由于最后需要的结果是单调不下降的
所以我们可以考虑贪心
设当前二分答案为Temp

• 若当前在，若 那么可以直接break掉，因为无解return false
• 若当前那么A[i]=min(A[i-1],A[i]+Temp)
• else可得A[i]=max(A[i]-Temp,A[i-1])

进而就OKay了。。。

代码

//P4105
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>

#define LL long long
#define Lowbit(X) (X&(-X))
#define Lson (X<<1)
#define Rson (X<<1|1)
#define Cl(X,Y) memset((X),(Y),sizeof(X))
#define FOR(i,A,B) for(LL i=A;i<=B;i++)
#define BOR(i,A,B) for(LL i=A;i>=B;i--)
#define FOR_SIDE(i,A) for(LL i=Head[A];i;i=Next[i])
#define INF 0x7fffffff
using namespace std;
const LL MAXN=5e6+10;

LL Total,A,B,C,D,Num[MAXN],MOD,F[MAXN];
LL Ans,Cop[MAXN];

inline void File() {
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
}

inline LL Function(LL New) {
    return (New*New%MOD*New%MOD*A%MOD+New*New%MOD*B%MOD+New*C%MOD+D)%MOD;
}

inline bool Check(LL Temp) {
    bool Vis=true;
    FOR(i,1,Total) {
        if(Cop[i]+Temp<Cop[i-1]) { Vis=false; break; }
        if(Cop[i]<=Cop[i-1]) Cop[i]=min(Cop[i-1],Cop[i]+Temp);
        else Cop[i]=max(Cop[i]-Temp,Cop[i-1]);
    }
    return Vis;
}

int main() {
    //File();
    scanf("%lld",&Total);
    scanf("%lld %lld %lld %lld",&A,&B,&C,&D);
    scanf("%lld %lld",&Num[1],&MOD);
    F[0]=Function(Num[0]);
    F[1]=Function(Num[1]);
    FOR(i,2,Total) {
        Num[i]=(F[i-1]+F[i-2])%MOD;
        F[i]=Function(Num[i]);
    }
    LL L=0,R=MOD;
    while(L<=R) {
        FOR(i,1,Total) Cop[i]=Num[i];
        Cop[0]=-INF;
        LL Mid=(L+R)>>1;
        if(Check(Mid)) R=Mid-1,Ans=Mid;
        else L=Mid+1;
    }
    printf("%lld\n",Ans);
    //fclose(stdin); fclose(stdout);
   // system("pause");
    return 0;
}