题意：有一个数组 ， 的值在 的整数中等概率随机，问最终
不降的概率。
答案对 取模，，时限 。
求出方案数后除以 即为概率。
首先不难想到一个 的
DP：
设 为 ，且 已填写的方案数。
有转移 可以前缀和优化。
但是本题
的范围很大，不可能完整记录在状态中。
注意到我们的限制只涉及到相对大小关系，考虑将 离散化，将值域分成 个左闭右开的段。
我们先将方案写成数组 ，其中 代表了 位于的段的编号，再考虑 对应的 的方案数。
对于 中的连续段 ，我们需要在第 段内选择 个不增的数，记第 个段内有 个数，方案数为 。
贡献系数和连续段长度有关，故设 为第 个数在第 个段内，且下一个数不在第
个段内的方案数。（这样可以控制每次转移的时一个机场连续段而不是部分连续段）
转移时枚举最后一个极长连续段 ： 前缀和优化即可做到 。
注意，组合数
的上标很大，无法预处理，需转为下降幂求解。
- 类似的题：Luogu3643 [APIO2016]划艇
另解
利用分段多项式函数。
设 表示前 个数已经确定，末尾为 的方案数，写出暴力 式 ：
可以证明
是分段的多项式函数，前面的做法就是一种构造证明。也可以通过前缀和变换归纳证明，这里就不详细展开了。
对于一个分段函数，我们要支持简单加法，以及
的点值前缀和计算。
不难发现点值前缀和就是离散微积分，为了方便积分，将多项式写成下降幂的形式即可。