快国赛了，写点水题玩吧。
首先容易有一个贪心策略：先以某种最优策略一直进行，直到成功一次后一直选择 \(b_i p_i\) 最大的进行。我们可以列出一个 DP，设 \(f_T\) 表示在 \(T\) 时刻内期望最大收益，容易写出：
\[f_T = \max \{p_i ((T - 1) v + a_i) + (1-p_i) f_{T - 1}\}
\]
看起来就是可以斜率优化的，整理可得：
\[f_T = f_{T - 1} + \max \{p_i ((T - 1) v - f_{T - 1}) + p_i a_i\}
\]
显然是可以斜率优化的，那么我们先把凸包建出来，然后考虑怎么做。
首先我们证明 \(k = Tv - f_T\) 是单调的。不难发现每次 \(k\) 会增加 \(v - (f_T - f_{T - 1})\)，而由于 \(a_i < b_i\)，那么说明一步之内能获得的最大收益就是 \(v\)，那么这个增加的数就一定是一个正数，于是说明这个 \(k\) 一定是单调递增的。
而根据斜率优化的结论，我们得知转移过程的所有最优决策点一定是划分成若干段，分别对应凸包上的一个点。上述的式子容易写成矩阵的形式，那么我们就可以直接矩阵快速幂二分到每个段的分割点即可。使用倍增就是单 \(\log\) 了。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
const double EPS = 1e-10;
int n;
long long T;
int a[MAXN], b[MAXN];
long double p[MAXN];
struct Matrix {
long double a[3][3];
Matrix() { memset(a, 0, sizeof a); }
static Matrix diag() { Matrix a; a[0][0] = a[1][1] = a[2][2] = 1; return a; }
long double* operator[](int b) { return a[b]; }
const long double* operator[](const int b) const { return a[b]; }
Matrix operator*(Matrix b) const {
Matrix c;
for (int k = 0; k < 3; k++)
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
c[i][j] += a[i][k] * b[k][j];
return c;
}
};
long double slope(int i, int j) {
if (p[i] == p[j]) return a[i] < a[j] ? INFINITY : -INFINITY;
return (a[j] * p[j] - a[i] * p[i]) / (p[j] - p[i]);
}
int stk[MAXN], top;
pair<long double, int> pt[MAXN];
long double v;
Matrix get(int i) {
Matrix m;
m[0][0] = 1 - p[i];
m[1][0] = p[i] * v, m[1][1] = 1;
m[2][0] = p[i] * a[i], m[2][1] = 1, m[2][2] = 1;
return m;
}
Matrix w[66];
long double value(Matrix m, int i) {
return p[i] * (m[2][1] * v - m[2][0]) + p[i] * a[i];
}
int main() {
scanf("%d%lld", &n, &T);
for (int i = 1; i <= n; i++) {
scanf("%d%d%Lf", &a[i], &b[i], &p[i]);
pt[i] = { p[i], i };
v = max(v, b[i] * p[i]);
}
sort(pt + 1, pt + 1 + n);
for (int i = 1; i <= n; i++) {
while (top > 1 && slope(stk[top], pt[i].second) - slope(stk[top - 1], stk[top]) > -EPS) top--;
stk[++top] = pt[i].second;
}
Matrix q = Matrix::diag();
for (int i = 1; i <= top; i++) if (T && (i == top || value(q, stk[i]) - value(q, stk[i + 1]) > -EPS)) {
w[0] = get(stk[i]);
for (int j = 1; j <= 60; j++) {
w[j] = w[j - 1] * w[j - 1];
}
for (int j = 60; j >= 0; j--) if (T > (1ll << j)) {
auto tmp = q * w[j];
long double f = tmp[2][0];
if (i == top || value(tmp, stk[i]) - value(tmp, stk[i + 1]) > -EPS) {
q = tmp;
T -= (1ll << j);
}
}
long double f = q[2][0];
q = q * w[0];
T--;
}
printf("%.12Lf\n", q[2][0]);
return 0;
}