令$Max=max_{i=1}^{n}p_{i}b_{i}$，显然这是每一个时刻的最大期望收益，因此当第一次胜利后，一定升级$Max$对应的这个游戏并一直玩，使得之后每一个时刻都取到这个最大期望收益
定义$f_{t}$表示可以玩$t$次的最大期望收益（初始状态下，即没有升级过任何游戏），转移考虑枚举第$t$个时刻玩的游戏，即$f_{t}=max_{i=1}^{n} p_{i}(a_{i}+(t-1)Max)+(1-p_{i})f_{t-1}$
简单变形，即$f_{t}=f_{t-1}+max_{i=1}^{n} p_{i}((t-1)Max-f_{t-1})+p_{i}a_{i}$
关于这个问题，即每一个游戏$i$对应于直线$l_{i}:y=p_{i}x+p_{i}a_{i}$，求$x=(t-1)Max-f_{t-1}$时的最大值
我们希望$x$有单调性，即$tMax-f_{t}ge (t-1)Max-f_{t-1}$，也即$Maxge f_{t}-f_{t-1}$
从定义的角度来看，考虑让$f_{t-1}$与$f_{t}$的前$t-1$次相同，显然最后一次的收益小于等于$Max$，即成立
由此，对这$n$条直线维护一个下凸壳，假设凸壳上的直线依次为$l_{b_{0}},l_{b_{1}},....,l_{b_{k}}$，其中直线$l_{b_{i}}$和$l_{b_{i+1}}$交点$x$坐标为$x_{i}$，问题即求$pos_{i}=max_{tMax-f_{t}le x_{i}}t+1$（特别的，$pos_{-1}=0$且$pos_{k}=infty$）
求出$pos_{i}$后，对于$tin (pos_{i-1},pos_{i}]$，都有$f_{t}=(1-p_{b_{i}})f_{t-1}+(t-1)p_{b_{i}}Max+p_{b_{i}}a_{b_{i}}$，显然可以用矩阵乘法维护，即
$$
left(egin{matrix}f_{t-1} &t-1&1\end{matrix}
ight)left(egin{matrix}1-p_{b_{i}} &0&0\p_{b_{i}}Max&1&0\p_{b_{i}}a_{b_{i}}&1&1\end{matrix}
ight)=left(egin{matrix}f_{t} &t&1\end{matrix}
ight)
$$
矩阵快速幂即可，复杂度为$o(nlog n)$
从前往后依次求$pos_{i}$，即已经求出$pos_{i-1}$和$f_{pos_{i-1}}$，现在来求$pos_{i}$
构造序列$egin{cases}g_{t}=f_{t}&(t=pos_{i-1})\g_{t}=g_{t-1}+p_{b_{i}}((t-1)Max-g_{t-1})+p_{b_{i}}a_{b_{i}}&(t>pos_{i-1})end{cases}$
与$f$类似，也有$tMax-g_{t}ge (t-1)Max-g_{t-1}$，具体证明类似，这里就省略了
由此，通过二分+矩阵快速幂，即可$o(log^{2}n)$求出$ans=max_{tMax-g_{t}le x_{i}}t+1$
由于在$tin [pos_{i-1},pos_{i}]$中$g_{t}=f_{t}$且$g_{pos_{i}+1}le f_{pos_{i}+1}$，不难证明$pos_{i}=ans$，即求出$pos_{i}$
总复杂度为$o(nlog^{2}n)$，可以通过
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 100005 4 #define ll long long 5 int n,x,st[N]; 6 ll t,pos[N]; 7 double Max,ans,f[N]; 8 struct Data{ 9 int a; 10 double p; 11 bool operator < (const Data &k)const{ 12 return (p<k.p)||(p==k.p)&&(a>k.a); 13 } 14 }a[N]; 15 double get(int x,int y){ 16 return (a[y].p*a[y].a-a[x].p*a[x].a)/(a[x].p-a[y].p); 17 } 18 struct matrix{ 19 double a[3][3]; 20 matrix(int p){ 21 memset(a,0,sizeof(a)); 22 if (p)a[0][0]=a[1][1]=a[2][2]=1; 23 } 24 }; 25 matrix mul(matrix x,matrix y){ 26 matrix z(0); 27 for(int i=0;i<3;i++) 28 for(int j=0;j<3;j++) 29 for(int k=0;k<3;k++)z.a[i][j]+=x.a[i][k]*y.a[k][j]; 30 return z; 31 } 32 matrix qpow(matrix n,ll m){ 33 matrix s=n,ans(1); 34 while (m){ 35 if (m&1)ans=mul(ans,s); 36 s=mul(s,s); 37 m>>=1; 38 } 39 return ans; 40 } 41 double calc(int i,ll n,ll lst,double ans){ 42 matrix A(1); 43 A.a[0][0]-=a[i].p; 44 A.a[1][0]=a[i].p*Max; 45 A.a[2][0]=a[i].p*a[i].a; 46 A.a[2][1]=1; 47 A=qpow(A,n-lst); 48 return A.a[0][0]*ans+A.a[1][0]*lst+A.a[2][0]; 49 } 50 int main(){ 51 scanf("%d%lld",&n,&t); 52 for(int i=1;i<=n;i++){ 53 scanf("%d%d%lf",&a[i].a,&x,&a[i].p); 54 Max=max(Max,a[i].p*x); 55 } 56 sort(a+1,a+n+1); 57 for(int i=1;i<=n;i++){ 58 if ((i>1)&&(a[i].p==a[i-1].p))continue; 59 while ((st[0]>1)&&(get(i,st[st[0]])<get(st[st[0]],st[st[0]-1])))st[0]--; 60 st[++st[0]]=i; 61 } 62 ll lst=0; 63 ans=0; 64 for(int i=1;i<st[0];i++){ 65 double x=get(st[i],st[i+1]); 66 if (lst*Max-ans>x)continue; 67 ll l=lst,r=t-1; 68 while (l<r){ 69 ll mid=(l+r+1>>1); 70 if (mid*Max-calc(st[i],mid,lst,ans)<=x)l=mid; 71 else r=mid-1; 72 } 73 l++; 74 ans=calc(st[i],l,lst,ans); 75 lst=l; 76 if (l==t){ 77 printf("%.8f",ans); 78 return 0; 79 } 80 } 81 printf("%.8f",calc(st[st[0]],t,lst,ans)); 82 }