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