Luogu P4105 [HEOI2014]南园满地堆轻絮

题目链接：传送门

明显的二分
简单的check
我的没有long long会炸掉50分

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <complex>
#include <algorithm>
#include <climits>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define A 5000010
#define B 2010

using namespace std;
typedef long long ll;
int n, sa, sb, sc, sd, a[A], mod;
ll F(ll x) {
	return ((sa * x % mod * x % mod * x % mod + sb * x % mod * x % mod) % mod + (sc * x % mod + sd) % mod) % mod;
}
bool check(int x, int maxx = 1) {
	for (int i = 1; i <= n; i++) {
		maxx = max(maxx, a[i] - x);
		if (maxx > a[i] + x) return false;
	}
	return true;
}

int main(int argc, char const *argv[]) {
	cin >> 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;
	int l = 1, r = mod;
	while (l <= r) {
		int m = (l + r) >> 1;
		if (check(m)) r = m - 1;
		else l = m + 1;
	}
	cout << l << endl;
}