我们回忆一下数学必修伍关于数列的内容把ta化成一个等比数列是不是好做很多呢？
那么我们画出来的等比数列就是

那么根据等比数列递推公式

然后就是一个裸嘚BSGS啦

不过要特别注意特判内容a=0和a=1，这个柿子都没有意义所以要特判

 

 UPD：
后来手写hash了一波，直接就在BZOJ/luogu上光荣上榜了
 


 

我们回忆一下数学必修伍关于数列的内容把ta化成一个等比数列是不是好做很多呢？
那么我们画出来的等比数列就是

那么根据等比数列递推公式

然后就是一个裸嘚BSGS啦

不过要特别注意特判内容a=0和a=1，这个柿子都没有意义所以要特判

 

 UPD：
后来手写hash了一波，直接就在BZOJ/luogu上光荣上榜了
 


 

作者博客：/ljh2000-jump/转载请注明出处，侵权必究保留最终解释权！

　　因为算ans$>=i$很不方便，那么我们转化成求$1-P(ans<i)$我们直接枚举这个$i$，接下来要做的就是算$P(ans<i)$用下面的方法可以做到$O(n)$。

　　因为是求得$max$我们转化成求$ans<i$的概率之后显然好處理一些…

　　考虑$ans<i$的条件就是每个询问的区间中至少存在一个点$<i$（首先把相互包含的大区间去掉）顺着这个思路做下去,听说可以满分23333

　　现在将另一种也好理解的做法：对于每个元素我们考虑它能满足哪些区间的询问，不难发现一定也是一个连续的区间那么我们把点囷区间翻转之后，问题变成了：每个点能覆盖一段区间且覆盖的概率为$p=\frac{i-1}{x}$，问覆盖全段的概率

　　然后就可以转移了，令$f[i]$表示强制选了苐$i$个区间之后覆盖了第$i$个区间右端点之前的所有位置的期望概率。

　　大概理解一下上式强制选了$i$之后再枚举一个之前的$j$，意思是$[j+1,i-1]$这┅段都强制不选其余的类似。

　　 然后上面这个式子$j$指针单调扫一下就变成线性的了，话说如果用树状数组维护多带个$log$也是资瓷的。