感受

思路




#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 6e6 + 10;
int n;
ll sa, sb, sc, sd, mod;
ll a[maxn], b[maxn];
ll quick_mod(ll a, ll n){
    ll sum = 1;
    while(n){
        if(n & 1) sum = sum * a % mod;
        a = a * a % mod;
        n /= 2;
    }
    return sum;
}
ll cal(ll x){
    return (((sa * quick_mod(x, 3) % mod + sb * quick_mod(x, 2) % mod) % mod + sc * x % mod) % mod + sd) % mod;
}
bool check(ll x){
    b[1] = a[1] - x;
    for(int i = 2; i <= n; i++){
        if(a[i] + x < b[i - 1]) return false;
        if(a[i] < b[i - 1]){
            b[i] = b[i - 1];
        }
        else{
            b[i] = max(b[i - 1], a[i] - x);
        }
    }
    return true;
}
void print(){
    for(int i = 1; i <= n; i++){
        printf("A[%d] = %lld\n", i, a[i]);
    }
}
int main(){
    scanf("%d%lld%lld%lld%lld%lld%lld", &n, &sa, &sb, &sc, &sd, &a[1], &mod);
    for(int i = 2; i <= n; i++){
        a[i] = cal(a[i - 1]) + cal(a[i - 2]); a[i] %= mod;
    }
    //print();
    ll l = -1, r = 2e9, mid;
    while(r - l > 1){
        mid = (l + r) / 2;
        if(check(mid)){
            r = mid;
        }
        else{
            l = mid;
        }
    }
    printf("%lld\n", r);
    return 0;
}