分析

出现了最大值最小这类关键字,一般要考虑二分答案。但首先我们必须考虑答案是否具有单调性。先钦定一个答案 。那么 。如果我们把绝对值符号拆开,这是由两个一次函数构成的,那么对于 。仍满足上式。所以这个是满足单调性的。考虑二分答案,只有两个限制需要考虑。 。当没法同时满足两个条件时,返回

代码

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 5000010;
LL n,Sa,Sb,Sc,Sd,mod;
LL A[N],B[N],F[N];
LL f(LL x) {
    return (1LL*Sa*x%mod*x%mod*x%mod+Sb*x%mod*x%mod+Sc*x%mod+Sd)%mod;
}
bool check(LL d) {
    memcpy(B,A,sizeof(B));
    B[1] = max(1LL,A[1]-d);
    for(int i = 2;i <= n;i++) {
        B[i] = max(B[i-1],A[i]-d);
        if(fabs(A[i]-B[i]) > d) return 0;
    }
    return 1;
}
int main() {
    A[0] = 0;
    scanf("%lld%lld%lld%lld%lld%lld%lld",&n,&Sa,&Sb,&Sc,&Sd,&A[1],&mod);
    A[1] %= mod;
    for(int i = 2;i <= n;i++) A[i] = (f(A[i-1]) + f(A[i-2]))%mod;
    LL r = mod+100,l = 0,ans = mod+100;
    while(l <= r) {
        LL mid = r+l >> 1;
        if(check(mid)) {
            ans = min(mid,ans);r = mid - 1;
        }
        else l = mid + 1;
    }
    cout << ans << endl;
    return 0;
}