题面
题解
设 \(A(l, r) = \sum_{i=l}^r a_i, B(l, r) = \sum_{i=l}^r b_i\)。
所求就是 \(\frac{2A(l, r)}{A(1, n) + B(l, r)}\)。
60 pts
分数规划，二分答案后有：\(2A(l, r) - \mathrm{mid} (A(l, r) + B(l, r)) \geq \mathrm{mid} * A(1, n)\)。
令 \(c_i = 2a_i - \mathrm{mid}(a_i + b_i)\)，跑一个最大子段和即可。
时间复杂度 \(\mathcal O(Tn\log n)\)。
100 pts
发现这两个序列 \(a, b\) 有周期且周期不超过 \(m\)。
所以答案要么不包含一个完整的周期，要么包含。
暴力枚举周期内的点，利用周期的性质计算答案。
时间复杂度 \(\mathcal O(Tm^2)\)。
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
inline int read()
{
int data = 0, w = 1; char ch = getchar();
while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
if (ch == '-') w = -1, ch = getchar();
while (ch >= '0' && ch <= '9') data = data * 10 + (ch ^ 48), ch = getchar();
return data * w;
}
const int N(105);
const double eps(1e-8);
int n, a[N << 1], pos[N], sum[N], p1, p2, M, tP, tS;
double ans;
int Query(int *P, int t, int i)
{
if (i <= 100) return P[i];
i -= 100 - t;
return (i / t) * (P[100] - P[100 - t]) + P[100 - t + (i % t)];
}
void GetAns(int l1, int r1, int l2, int r2)
{
for (int i = l1; i <= r1; i++)
for (int j = std::max(i + 1, l2); j <= r2; j++)
ans = std::max(ans, 1. * (Query(pos, tP, j) - Query(pos, tP, i)) /
(Query(pos, tP, n) + Query(sum, tS, j) - Query(sum, tS, i)));
}
int main()
{
#ifndef ONLINE_JUDGE
file(cpp);
#endif
while ((n = read()))
{
a[1] = read(), p1 = read(), p2 = read(), M = read(), ans = 0.;
for (int i = 2; i <= 200; i++) a[i] = (a[i - 1] * p1 + p2) % M;
for (int i = 1; i <= 100; i++)
sum[i] = (pos[i] = a[(i << 1) - 1]) + a[i << 1];
for (int i = 1; i < 60; i++)
if (pos[40] == pos[i + 40]) { tP = tS = i; break; }
for (int i = 1; i <= 100; i++)
pos[i] += pos[i - 1], sum[i] += sum[i - 1];
GetAns(0, std::min(100, n), 0, std::min(100, n));
GetAns(0, std::min(100, n), std::max(0, n - 100), n);
printf("%.6lf\n", ans * 2);
}
return 0;
}